Γράφημα

[Mathletic]

Γειά

Πώς υπολογίζεται η διάμετρος ενός συνεκτικού διμερούς γραφήματος;

Η διάμετρος είναι η μέγιστη των ελαχίστων αποστάσεων δύο κόμβων.

Έστω και τα σύνολα των κορυφών. ( )
Η μέγιστη δυνατή διαδρομή είναι , ή κάνω λάθος;
Είναι η διάμετρος ;

[Demetres]

Δεν μας είπες ποιες είναι οι ακμές.

[Mathletic]

Δεν μας είπες ποιες είναι οι ακμές.

Οι ακμές της μέγιστης δυνατής διαδρομής είναι: .

Ή κάνω λάθος;

[Demetres]

Επαναλαμβάνω: Ποιες είναι οι ακμές του διμερούς γραφήματος;

Π.χ. αν το γράφημα είναι πλήρες διμερές τότε η διάμετρος ισούται με . Αν το γράφημα είναι μονοπάτι μήκους τότε η διάμετρος ισούται με .

[Mathletic]

Επαναλαμβάνω: Ποιες είναι οι ακμές του διμερούς γραφήματος;

Π.χ. αν το γράφημα είναι πλήρες διμερές τότε η διάμετρος ισούται με . Αν το γράφημα είναι μονοπάτι μήκους τότε η διάμετρος ισούται με .

Δεν είναι δεδομένο αν το γράφημα είναι πλήρες ή όχι.

Αν το γράφημα είναι πλήρες διμερές, κάθε κόμβος του συνόλου συνδέεται με όλους κόμβους του συνόλου , γιατί τότε η διάμετρος δεν είναι ;

Όταν το γράφημα δεν είναι πλήρες, τότε ισούται η διάμετρος με ;