περίεργος κύκλος σε γράφημα

[maougrim]

Δείξτε ότι καθε γράφημα G με n κορυφές και τουλάχιστον 2n ακμές περιέχει κύκλο μήκους το πολύ

[Demetres]

Η άσκηση πρέπει να είναι λανθασμένη. Για παράδειγμα αν πάρουμε το γράφημα που αποτελείται από την ένωση ξένων μεταξύ τους , τότε το γράφημα έχει κορυφές, ακμές, αλλά κάθε κύκλος του έχει μήκος το πολύ 5.

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

Από που την πήρες την άσκηση;

[maougrim]

η άσκηση είναι από φυλλάδιο ασκήσεων του μαθηματικού τμήματος πανεπιστημίου Αθηνών στο μάθημα Θεωρία Γραφημάτων

μάλλον όντως χαλασμένη πρέπει να είναι γιατί αν έχεις 3 κυκλους μήκους 3 το δε βγαίνει ακέραιος

[maougrim]

λογικά θα είναι σωστή τώρα

[Demetres]

λογικά θα είναι σωστή τώρα

Ναι, τώρα η άσκηση είναι σωστή. Μιας και είναι άσκηση για το σπίτι, θα δώσω μόνο υπόδειξη:

Προσπάθησε πρώτα να αποδείξεις ότι κάθε γράφημα με κορυφές όπου κάθε κορυφή έχει βαθμό τουλάχιστον 3, έχει ένα κύκλο μήκους το πολύ .

[maougrim]

Προσπάθησε πρώτα να αποδείξεις ότι κάθε γράφημα με κορυφές όπου κάθε κορυφή έχει βαθμό τουλάχιστον 3, έχει ένα κύκλο μήκους το πολύ .

μου φαίνεται αν πάρω 2 κύκλους μήκους 3 και συνδέσω τις κορυφές τους θα πάρω ενα γράφημα που θα έχει κύκλο μήκους

[Demetres]

Προσπάθησε πρώτα να αποδείξεις ότι κάθε γράφημα με κορυφές όπου κάθε κορυφή έχει βαθμό τουλάχιστον 3, έχει ένα κύκλο μήκους το πολύ .

μου φαίνεται αν πάρω 2 κύκλους μήκους 3 και συνδέσω τις κορυφές τους θα πάρω ενα γράφημα που θα έχει κύκλο μήκους

Ναι αλλά έχει και ένα κύκλο μήκους . Το μόνο που θέλουμε να δείξουμε είναι ότι το γράφημα έχει ένα κύκλο με λίγες κορυφές. Δεν θέλουμε να δείξουμε ότι κάθε κύκλος έχει λίγες κορυφές.

[maougrim]

με δυσκολεύει αρκετά αυτή η άσκηση , νομίζω ότι ο λόγος για τον οποίο δημιουργούνται αυτοί οι μικροί κύκλοι είναι ο υπερβολικά μεγάλος αριθμός των ακμών σε σχέση με το πλήθος των κορυφών αλλά δεν βρίσκω κάποιο συγκεκριμένο σημείο να πιαστώ

[Demetres]

Η λύση της άσκησης βασίζεται σε δύο ιδέες.

Η πρώτη είναι η διαπίστωση ότι αρκεί να αποδειχθεί η άσκηση που έβαλα. Αντί δηλαδή να γνωρίζουμε πως το γράφημα έχει αρκετές ακμές να γνωρίζουμε πως κάθε κορυφή του γραφήματος έχει αρκετές γειτονικές κορυφές.

Πως το κάνουμε αυτό; Γνωρίζουμε ότι το γράφημα έχει κορυφές και τουλάχιστον ακμές. Ας αφαιρέσουμε μια κορυφή που έχει το πολύ 2 γειτονικές κορυφές. Θα πάρουμε ένα γράφημα με κορυφές και το πολύ ακμές. Επαναλαμβάνουμε. Στο τέλος θα έχουμε ένα γράφημα με κορυφές, τουλάχιστον ακμές έτσι ώστε κάθε κορυφή έχει τρεις άλλες γειτονικές κορυφές. Αν δείξουμε πως αυτό το γράφημα έχει κύκλο μήκους το πολύ τότε τελειώσαμε.

Τα πράγματα τώρα είναι πιο εύκολα. Έστω ότι ο μικρότερος κύκλος του γραφήματος έχει μήκος . Ας υποθέσουμε ότι . Έστω μια κορυφή του γραφήματος, το σύνολο όλων των κορυφών που είναι γειτονικές με την , το σύνολο όλων των κορυφών που είναι γειτονικές με τις κορυφές του συνόλου κ.τ.λ. Τι μπορείς να πεις για το μέγεθος του ; Τι μπορείς να πεις για το μέγεθος του και γιατί; Για τα μεγέθη των ;