Ένα εκτεινόμενο υπογράφημα είναι ένα υπογράφημα που περιέχει όλες τις κορυφές του αρχικού γραφήματος. Ένα εκτεινόμενο δέντρο είναι ένα εκτεινόμενο υπογράφημα που συχνά παρουσιάζει ενδιαφέρον. Ένας κύκλος σε ένα γράφημα που περιέχει όλες τις κορυφές του γραφήματος θα ονομαζόταν εκτεινόμενος κύκλος.
Πόσες εκτείνουσες υπογραφές υπάρχουν;
Υπάρχουν 2n επαγόμενες υπογραφές (όλα τα υποσύνολα κορυφών) και 2m που εκτείνονται σε υπογραφήματα (όλα τα υποσύνολα των ακμών).
Πώς μπορώ να βρω ένα εκτεταμένο υπογράφημα;
Και εξ ορισμού του Εκτεινόμενου υπογράφου ενός γραφήματος G είναι ένα υπογράφημα που λαμβάνεται μόνο με διαγραφή άκρων. Αν κάνουμε υποσύνολα ακμών διαγράφοντας μια ακμή, δύο ακμές, τρεις ακμές και ούτω καθεξής. Καθώς υπάρχουν m άκρες έτσι υπάρχουν και 2^m υποσύνολα. Ως εκ τούτου, το G έχει υπογραφήματα 2^m.
Τι εννοείται με τον όρο spanning tree;
Το εκτεινόμενο δέντρο ενός γραφήματος (G) είναι ένα υποσύνολο του G που καλύπτει όλες τις κορυφές του χρησιμοποιώντας τον ελάχιστο αριθμό ακμών. Ορισμένες ιδιότητες ενός εκτεινόμενου δέντρου μπορούν να συναχθούν από αυτόν τον ορισμό: Εφόσον "ένα εκτεινόμενο δέντρο καλύπτει όλες τις κορυφές", δεν μπορεί να αποσυνδεθεί.
Τι είναι η εκτεινόμενη θεωρία γραφημάτων;
Ένα εκτεινόμενο δέντρο είναι ένα υποσύνολο του Γραφήματος G, το οποίο έχει όλες τις κορυφές καλυμμένες με τον ελάχιστο δυνατό αριθμό ακμών. Επομένως, ένα εκτεινόμενο δέντρο δεν έχει κύκλους και δεν μπορεί να αποσυνδεθεί. Με αυτόν τον ορισμό, μπορούμε να βγάλουμε ένα συμπέρασμα ότι κάθε συνδεδεμένο και μη κατευθυνόμενο γράφημα G έχει τουλάχιστον ένα εκτείνοντα δέντρο.
