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

Νοέμβριος 3, 2008

Πώς να συνδέσουμε τα μηχανήματα;

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 12:41 πμ

Στο Τμήμα Μαθηματικών του Πανεπιστημίου Κρήτης κατασκευάζουμε μια αίθουσα με υπολογιστές. Αυτή έχει μέσα δύο πάγκους, τον Α και τον Β, και ο καθένας από αυτούς έχει επάνω κάποια μηχανήματα. Κάθε μηχάνημα έχει 4 τρόπους να συνδεθεί με άλλο μηχάνημα: USB, ethernet, serial και parallel. Για κάθε ένα από αυτούς τους τρόπους μπορεί να συνδεθεί με το πολύ ένα μηχάνημα (point to point).

O sysadmin μας έχει αποφασίσει ποια μηχανήματα του πάγκου Α θα πρέπει να συνδεθούν με ποια του πάγκου Β. Ξέρουμε δηλ. για κάθε μηχάνημα του πάγκου Α με ποια (το πολύ τέσσερα) μηχανήματα του πάγκου Β πρέπει να συνδεθεί και ομοίως για τα μηχανήματα του πάγκου Β. Δεν τον ενδιαφέρει με ποιο τρόπο από τους τέσσερεις επιτρεπτούς θα συνδεθεί το κάθε ζεύγος.

Δείξτε ότι οι απαιτήσεις αυτές του sysadmin μπορούν να ικανοποιηθούν.

Advertisements

4 Σχόλια »

  1. Διατυπώστε το πρόβλημα σαν ένα πρόβλημα χρωματισμού των ακμών ενός γραφήματος.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Νοέμβριος 9, 2008 @ 10:33 πμ

  2. Τώρα δεν ξέρω αν αυτό είναι πρόβλημα προς λύση ή σπαζοκεφαλιά. Εγώ θα έβαζα ένα 48port switch και θα τα ένωνα όλα με ethernet και λήξης.

    Μου αρέσει!

    Σχόλιο από moses12315 — Νοέμβριος 11, 2008 @ 9:44 μμ

  3. ‘Εχουμε ενα διμερές γράφημα λοιπον οπου θέλουμε να βάψουμε τις ακμες του με βαση τον τροπο συνδεσης και εχουμε 4-χρωματα. Θα δείξουμε οτι μας αρκουν τα 4-χρωματα για να το βαψουμε. Οι κορυφές του γραφήματος εχουν βαθμό το πολυ 4. Θα δείξουμε το ζητούμενο με επαγωγή ως προς το πλήθος τον ακμών(|Ε|).
    Για |Ε|= 1 μου αρκει ενα χρώμα οποτε ισχύει.
    Εστω οτι ισχύει για |Ε|<=κ, θα δειξω πως ισχύει για κ+1.
    Εχω το γράφημα G(V,E) με |Ε|=κ+1. Σβήνω μια ακμή, την {x,y} οπότε μένουν κ ακμές και απο την επαγωγική μου υπόθεση μου αρκουν τα 4-χρωματα για να βαψω. Στο καινούριο γραφημα που εχει προκύψει το G’=G\{x,y} οι ακμές x και y εχουν βαθμό το πολύ 3. Αν το χρώμα ακμής που λείπει στις x,y ειναι το ιδιο τοτε βαφω με αυτο και εχω τελειωσει.
    Αν ειναι διαφορετικο τοτε αλλάζουμε το χρωματισμό ακμών του G’ ως εξής (αλυσίδες Kempe):
    εστω, χωρίς βλάβη της γενικοτητας, πως απο την κορυφή x λειπει το χρωμα 1 και απο την κορυφή y το χρώμα 2. Ξεκινάμε απο την κορυφή x και περναμε απεναντι ακολουθώντας την ακμή της χρώματος 2, φτάνουμε ετσι σε καποια κορυφή της πλευράς Β. Εαν αυτη η κορυφή εχει ακμή χρώματος 1, τοτε την ακολουθούμε και περναμε στην κορυφη της πλευράς Α που καταλήγει η ακμή. απο εκει αν υπαρχει ακμη χρώματος 2 την ακολουθουμε και συνεχιζουμε κατ’αυτο τον τροπο μεχρι να βρεθούμε σε κάποια ακμή που θα της λείπει το χρωμα που χρειαζομαστε για να προχωρήσουμε. Εκει σταματάμε και αλλαζουμε σε ολες τις ακμες της διαδρομής μας το χρωμα 1 με το χρώμα 2 (και το χρώμα 2 με το χρώμα 1).
    Προσέξτε πως κατα την αλλαγη του χρωματισμου δεν παραβιάζουμε τον κανονα χρωματισμού μας, αφου στην τελευταία ακμη λείπει το καινούριο χρώμα που της δείνουμε και σε ολες τις ενδιαμεσες εχουμε ενναλλαξει τα χρωματα δύο ακμών τους μεταξύ τους, οποτε το βαψιμο μας ειναι δεκτο κ πλεον η κορυφή x και η κορυφή y μπορούν να ενωθούν με το χρώμα 2 που πλέον λείπει και απο τις δύο.

    Μου αρέσει!

    Σχόλιο από georgepapakir — Νοέμβριος 24, 2008 @ 2:36 μμ

  4. Πολύ σωστά.

    Αυτό που έδειξες είναι ένα θεώρημα του Koenig (1916), το οποίο λέει ότι σε ένα διμερές γράφημα με μέγιστο βαθμό κορυφής Δ μπορούμε να χρωματίσουμε τις ακμές του με, το πολύ, Δ διαφορετικά χρώματα, με τέτοιο τρόπο ώστε δύο ακμές που καταλήγουν στην ίδια κορυφή να έχουν διαφορετικό χρώμα.

    Το κόλπο με τις αλυσίδες Kempe (maximal αλυσίδες με εναλασσόμενα χρώματα) είχε πρωτοεισαχθεί από τον Kempe σε μια αποτυχημένη προσπάθειά του να αποδείξει το περίφημο θεώρημα των τεσσάρων χρωμάτων (κάθε επίπεδος χάρτης μπορεί να χρωματιστεί με 4 χρώματα ούτως ώστε δύο χώρες που συνορεύουν να έχουν αναγκαστικά διαφορετικό χρώμα).

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Νοέμβριος 24, 2008 @ 3:44 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

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