Το γράφημα αποτελείται από κορυφές και άκρα. Οι κορυφές συνδέονται με άκρα σύμφωνα με μια συγκεκριμένη ιδιότητα - τη σχέση επίπτωσης, η οποία καθορίζει το σύνολο των άκρων. Σε αυτήν την περίπτωση, μπορούν να σχηματιστούν βρόχοι και απομονωμένες κορυφές.
Οδηγίες
Βήμα 1
Αφήστε το σύνολο των άκρων του γραφήματος και δοθεί η σχέση κατά την οποία είναι δυνατόν να τραβήξετε ένα άκρο από τη μία κορυφή στην άλλη. Για παράδειγμα, το σύνολο κορυφών {1, 2, 3, 4, 5, 6, 7, 8}, δύο κορυφές x και y είναι στην αναλογία x + y <8.
Βήμα 2
Δημιουργήστε μια μήτρα γειτονίας κορυφών. Για να το κάνετε αυτό, δημιουργήστε έναν τετράγωνο πίνακα, ο αριθμός των γραμμών και στηλών στον πίνακα συμπίπτει με τον αριθμό των κορυφών. Στη συνέχεια, τοποθετήστε το 1 στη διασταύρωση της γραμμής i-th και της στήλης j-th εάν οι κορυφές i και j ικανοποιούν τη δεδομένη αναλογία. Βάλτε 0 στη διασταύρωση της γραμμής i-th και της στήλης j-th εάν η αναλογία για τα αντίστοιχα στοιχεία δεν ικανοποιείται.
Στο παράδειγμά μας, η πρώτη γραμμή συμπληρώνεται ως εξής:
1 + 1 <8, οπότε υπάρχει 1 στη διασταύρωση της 1ης σειράς και της 1ης στήλης
1 + 2 <8, ξανά 1
1 + 3 <8, ξανά 1
1 + 7 <8, εσφαλμένη ανισότητα, επομένως αυτό το στοιχείο του πίνακα θα είναι 0
1 + 8 <8, ξανά 0
Βήμα 3
Για να μάθετε τον αριθμό των άκρων, μετρήστε τον αριθμό αυτών στον πίνακα γειτνίασης χωρίς να αντιγράψετε τις άκρες.
Στο παράδειγμα, ελήφθη μια συμμετρική μήτρα, οπότε μετρήσαμε πρώτα αυτές που βρίσκονται πάνω από την κύρια διαγώνια της μήτρας (επισημαίνονται με μπλε χρώμα) και μετά αυτές που βρίσκονται στην κύρια διαγώνια (σημειώνονται με κόκκινο χρώμα). Ο συνολικός αριθμός νευρώσεων είναι 12.
Βήμα 4
Δημιουργήστε έναν πίνακα συμβάντων (άκρα). Για να το κάνετε αυτό, σχεδιάστε έναν πίνακα, ο αριθμός των σειρών σε αυτόν είναι ίσος με τον αριθμό των κορυφών στο γράφημα και ο αριθμός των στηλών είναι ίσος με τον αριθμό των άκρων. Βάλτε μονάδες σε αυτές τις γραμμές που θα συνδεθούν με ένα άκρο Οι άκρες που οδηγούν από την κορυφή προς αυτό ονομάζονται βρόχοι και προστίθενται στο τέλος της μήτρας. Στις στήλες που αντιστοιχούν στους βρόχους, υπάρχει μόνο μία μονάδα, σε αντίθεση με τις υπόλοιπες ακμές.
Βήμα 5
Τώρα σχεδιάστε ένα γράφημα. Τοποθετήστε τις κορυφές στο χαρτί με οποιονδήποτε τρόπο και συνδέστε τις με τις άκρες χρησιμοποιώντας τα κατασκευασμένα τραπέζια. Οι κορυφές που δεν συνδέονται με άκρα ονομάζονται απομονωμένες.
