Προβλήματα Μαθηματικών

Απρίλιος 6, 2008

Το πεπερασμένο και το άπειρο

Filed under: Άλυτα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 3:27 μμ

Ένα γράφημα G είναι ένα σύνολο V από κορυφές οι οποίες μπορεί ανά δύο να συνδέονται με μια ακμή. (Αυτό κωδικοποιείται στο σύνολο E των ακμών που είναι ένα σύνολο από διμελή υποσύνολα του V.)

Ένα απλό γράφημα

Ένας χρωματισμός ενός γραφήματος με {r} χρώματα είναι μια απεικόνιση

\displaystyle \chi:V \to \{1,\ldots,r\}

τέτοια ώστε αν οι κορυφές u, v \in V συνδέονται με ακμή στο γράφημα (αν δηλ. \{u,v\}\in E) τότε \chi(u) \neq \chi(v). Κορυφές δηλ. που συνδέονται με ακμή πρέπει να έχουν διαφορετικό χρώμα.

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

Σας δίδεται ένα γράφημα G με άπειρο σύνολο κορυφών V=\{1,2,3,\ldots\} και με την ιδιότητα ότι όλα τα πεπερασμένα υπογραφήματά του μπορούν να χρωματιστούν με 10 χρώματα. Δείξτε ότι το ίδιο ισχύει και για το άπειρο γράφημα G.

Advertisements

11 Σχόλια »

  1. Υπόδειξη:

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

    Προσπαθείστε να βρείτε ένα χρωματισμό του άπειρου γραφήματος ως εξής: ας είναι {G_n} το πεπερασμένο υπογράφημα του {G} που ορίζεται από τις κορυφές {1,2,\ldots,n} και τις ακμές του {G} που τις ενώνουν μεταξύ τους, και ας είναι

    {\chi_n:\{1,2,\ldots,n\} \to \{1,2,\ldots,r\}}

    ένας καλός χρωματισμός του {G_n} (που αντιστοιχεί δηλ. διαφορετικά χρώματα σε κορυφές που συνδέονται με ακμή στο {G_n}).

    Τα στοιχεία της άπειρης ακολουθίας

    { \chi_1(1), \chi_2(1), \ldots, \chi_n(1), \ldots }

    παίρνουν το πολύ {r < \infty} διαφορετικές τιμές, άρα υπάρχει κάποιο χρώμα {c_1 \in \{1,2,\ldots r \}} που εμφανίζεται σε αυτή την ακολουθία άπειρες φορές. Επιλέξτε το {c_1} ως χρώμα της κορυφής 1.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Απρίλιος 20, 2008 @ 11:04 μμ

  2. Υπόδειξη:

    Έχοντας επιλέξει το c_1 ως το χρώμα της κορυφής 1, «πετάξτε» από το σύνολο των φυσικών αριθμών n όλα εκείνα τα n για τα οποία ο χρωματισμός \chi_n δίνει στην κορυφή 1 χρώμα διαφορετικό από το c_1. Από τον τρόπο επιλογής του χρώματος c_1 (δείτε αμέσως προηγούμενο σχόλιο-υπόδειξη) προκύπτει ότι απομένουν άπειρα ακόμη n. Από δω και πέρα δουλεύετε μόνο με αυτά τα n.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 8, 2009 @ 10:19 μμ

  3. Τί συμβολίζει κάθε στοιχείο της άπειρης ακολουθίας στο πρώτο σχόλιο; Δεν καταλαβαίνω τί είναι το (1) που εμφανίζετε σε κάθε στοιχείο. Ευχαριστώ.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Σεπτεμβρίου 5, 2015 @ 12:29 πμ

  4. Είναι το σύνολο κορυφών κάθε πεπερασμένου υπογραφήματος που παίρνουν το 1ο χρώμα;

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Σεπτεμβρίου 5, 2015 @ 12:47 πμ

  5. 3, 4: Το 1 είναι η κορυφή 1 (στοιχείο του συνόλου V). \chi_n(1) είναι το χρώμα που παίρνει η κορυφή 1 υπό το χρωματισμό \chi_n.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 5, 2015 @ 7:55 πμ

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

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Σεπτεμβρίου 10, 2015 @ 4:19 μμ

  7. 6: Ποιος μίλησε για «βέλτιστο καλό χρωματισμό»; Το πρόβλημα είναι μια χαρά ορισμένο.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 10, 2015 @ 4:21 μμ

  8. Παραθέτω μια σκιαγράφηση εύχομαι να τη συμπληρώσω σύντομα.
    (Συνέχεια στο 2) Αφού έχουμε κρατήσει μόνα αυτά τα n, τα οποία χρωματίζουν την κορυφή 1 με το χρώμα c_1 σε κάθε χρωματισμό \chi_{n}, αναλογιζόμαστε την ακολουθία: {\chi_1(2),\chi_2(2),\chi_3(2),\ldots,\chi_n(2),\ldots} (*). Αυτή είναι ξανά μια άπειρη ακολουθία, οπότε υπάρχει κάποιο c_2\in\{1,2,\ldots,r\}, (c_2\neq c_1) το οποίο εμφανίζεται στην (*) άπειρες φορές. Με το c_2 χρωματίζουμε όλες τις κορυφές του άπειρου γραφήματος που έχουν ακμή που τις συνδέει με την κορυφή 1. Το c_2, δεν εξαντλείται μόνο σε αυτές τις κορυφές. Αγνοούμε όλα τα n, για τα οποία ο χρωματισμός \chi_{n} δίνει στις κορυφές 1 και 2 χρώματα διαφορετικά από c_1 και c_2 αντίστοιχα. Απομένουν άπειρα ακόμη n. Με τον ίδιο τρόπο παίρνουμε ένα c_3 \in \{\{1,2,\ldots,r\}\backslash \{c_1,c_2\}\} και χρωματίζουμε με αυτό όλες τις κορυφές που σχηματίζουν κύκλο μήκους 3 με τις κορυφές 1 & 2.
    Οποιαδήποτε σχόλια ευπρόσδεκτα.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Σεπτεμβρίου 11, 2015 @ 2:46 μμ

  9. Διόρθωση: Με το c_2 χρωματίζουμε όλες τις κορυφές του άπειρου γραφήματος που ανά δύο δεν συνδέονται μεταξύ τους και όλες έχουν ακμή που τις συνδέει με την κορυφή 1. Ομοίως και για το c_3. Καμία από τις κορυφές που χρωματίζονται με το c_3 δεν πρέπει να συνδέονται ανά δύο μεταξύ τους.
    Να σημειωθεί επίσης ότι το άπειρο γράφημα δεν έχει υπογράφημα που να είναι πλήρες γράφημα με 10 κορυφές (σε αυτή τη περίπτωση 11 χρώματα θα χρειαζόντουσαν).

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Σεπτεμβρίου 11, 2015 @ 3:39 μμ

  10. 8,9:

    Γιατί πρέπει c_2 \neq c_1;

    Με το χρωματισμό που φτιάχνεις γιατί χρωματίζονται όλες οι κορυφές τελικά αφού, όπως λες, «Με το c_2 χρωματίζουμε όλες τις κορυφές του άπειρου γραφήματος που έχουν ακμή που τις συνδέει με την κορυφή 1.»

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 12, 2015 @ 12:31 μμ

  11. 10: Δεν ισχυρίζομαι ότι με αυτά τα δύο χρώματα πέτυχα τον χρωματισμό του άπειρου γραφήματος. Η προσέγγιση που πήρα, έτσι όπως αντιλαμβάνομαι το πρόβλημα είναι αφού έχουμε δείξει την ύπαρξη κάποιου χρώματος που εμφανίζεται άπειρες φορές (υπάρχουν άπειρα πεπερασμένα συνεκτικά κομμάτια-υπογραφήματα όπου μπορεί μια κορυφή να εμφανίζεται και συνεπώς άπειροι χρωματισμοί) υπό διαφορετικούς χρωματισμούς σε μια οποιαδήποτε κορυφή (την ονομάσαμε 1 – δεν προσδιορίσαμε που είναι τοποθετημένη στο άπειρο γράφημα), δίνουμε το χρώμα αυτό σε αυτή την κορυφή και ακολούθως αγνοούμε όλους τους χρωματισμούς – όλα τα n, για τα οποία ο χρωματισμός \chi_{n} δίνει χρώμα διαφορετικό από το c_1 στην κορυφή 1. Από τον τρόπο επιλογής του c_1 υπάρχουν άπειρα ακόμη τέτοια n. Κατόπιν βρίσκουμε όλες τις κορυφές που είναι συνδεδεμένες με ακμή με την κορυφή 1 αλλά που να μην συνδέονται ανά δύο μεταξύ τους και τις χρωματίζουμε με ένα άλλο χρώμα (για να είναι ο χρωματισμός εντάξει) που έχουμε στη διάθεσή μας (γνωρίζουμε ότι όλα τα πεπερασμένα υπογραφήματα μπορούν να έχουν καλό χρωματισμό με 10 χρώματα). Μετά παίρνουμε ακόμη ένα διαφορετικό χρώμα και κάνουμε ανάλογη διαδικασία και διαδοχικά αποκλείουμε τα n που προσδίδουν χρωματισμούς διαφορετικούς στα υπογραφήματα που επάγονται από τις κορυφές που έχουν ήδη πάρει χρώμα.
    Δεν βλέπω όμως κατασκευαστικό τρόπο να χρωματιστεί το άπειρο γράφημα.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Σεπτεμβρίου 12, 2015 @ 1:46 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: