Άρθρα

5. S: Θεωρία γραφήματος (Περίληψη)


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

Ένας λόγος για τον οποίο η θεωρία του γραφήματος είναι μια τόσο πλούσια περιοχή μελέτης είναι ότι ασχολείται με μια τόσο θεμελιώδη έννοια: κάθε ζευγάρι αντικειμένων μπορεί είτε να σχετίζεται είτε όχι. Τι είναι τα αντικείμενα και τι σημαίνει "σχετικό" ποικίλλει ανάλογα με το πλαίσιο, και αυτό οδηγεί σε πολλές εφαρμογές της θεωρίας γραφημάτων στην επιστήμη και σε άλλους τομείς των μαθηματικών. Τα αντικείμενα μπορεί να είναι χώρες και δύο χώρες μπορούν να συσχετιστούν εάν μοιράζονται σύνορα. Τα αντικείμενα θα μπορούσαν να είναι μάζες εδάφους που σχετίζονται αν υπάρχει μια γέφυρα μεταξύ τους. Τα αντικείμενα θα μπορούσαν να είναι ιστοσελίδες που σχετίζονται αν υπάρχει σύνδεσμος μεταξύ τους. Ή μπορούμε να είμαστε εντελώς αφηρημένοι: τα αντικείμενα είναι κορυφές που σχετίζονται αν είναι ένα άκρο μεταξύ τους.

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

  • Μπορεί το γράφημα να σχεδιαστεί στο επίπεδο χωρίς να διασχίζουν τα άκρα; Εάν ναι, σε πόσες περιοχές χωρίζει το σχέδιο αυτό το επίπεδο;
  • Είναι δυνατόν να χρωματίσετε τις κορυφές του γραφήματος έτσι ώστε οι σχετικές κορυφές να έχουν διαφορετικά χρώματα χρησιμοποιώντας μικρό αριθμό χρωμάτων; Πόσα χρώματα χρειάζονται;
  • Είναι δυνατόν να ανιχνεύσετε πάνω από κάθε άκρο ενός γραφήματος μία φορά χωρίς να σηκώσετε το μολύβι σας; Ποια άλλα είδη «διαδρομών» μπορεί να έχει ένα γράφημα;
  • Μπορείτε να βρείτε υπογράφους με συγκεκριμένες ιδιότητες; Για παράδειγμα, πότε ένα (διμερές) γράφημα περιέχει έναν υπογράφο στον οποίο όλες οι κορυφές σχετίζονται μόνο με μια άλλη κορυφή;

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

Επανεξέταση κεφαλαίου

1

Ποια (εάν υπάρχουν) από τα παρακάτω γραφήματα είναι τα ίδια; Ποια είναι διαφορετικά; Εξηγώ.

Λύση

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


Δες το βίντεο: Was ist die 5S Methode? (Δεκέμβριος 2021).