| Τοπολογική Διάταξη και Ισχυρά Συνεκτικές Συνιστώσες: Παιδιά καλημέρα συνεχίζουμε μου της διάλεξη στο μάθημα εισαγωγής αλγόριθμους με την έβδομη ενότητα η οποία περιλαμβάνει αλγόριθμους γραφημάτων για δύο πολύ σημαντικά προβλήματα το ένα είναι η τοπολογία διάταξη και το άλλο είναι ισχυρά συνεκτικές συνιστώσες από πριν ξεκινήσουμε να θυμίσω μάλλον ότι στις δύο προηγούμενες ενότητες έχουμε δει το μοντέλο των γραφημάτων ποσού μαθηματικό μοντέλο τις βασικές ιδιότητες του την αναπαράσταση του στη μνήμη του υπολογιστή και έχουμε δει βασικούς αλγόριθμους διερεύνησης αναζήτησης πάνος γραφήματα αυτές οι δύο βασικές μέθοδοι και η αναζήτηση πρώτα κατά πλάτος και η αναζήτηση πρώτα καταβάθος είναι θεμελιώδης και θα τις χρησιμοποιήσουμε θα το δείτε αυτό στο σημερινό μάθημα προκειμένου να δημιουργήσουμε και άλλους αλγόριθμους για προβλήματα τα οποία θα μας απασχολούν έχουμε ήδη δει ένα εφαρμογή της αναζήτησης πρώτα κατά βάθος για την εύρεση συνεκτικών συνιστωσών σε μη κατευθυνόμενο γράφημα και επίσης έχουμε δει την αναζήτηση μια εφαρμογή της αναζήτησης πρώτα κατά πλάτος στον έλεγχο του κατά πόσον ένα κατευθυνόμενο γράφημα είναι ισχυρά συνεκτικό η όχι ωραία σήμερα πώς λοιπόν θα δούμε δύο αλγόριθμους για δύο άλλα προβλήματα τα οποία είναι πάρα πολύ σημαντικά στα κατευθυνόμενα γραφήματα και ξεκινάμε από το κάτι κατευθύνονται ΟΠΑΠ ΟΠΑΠ το ζήτημα από το πρόβλημα στο Μπόινγκ της διάταξης το φορολογική διάταξη δεν είναι τίποτε άλλο παρά ένα αρίθμηση ας δούμε έτσι των κορυφών ένα γραφημάτων ως έτσι ώστε για κάθε πλευρά διαρρύθμιση που θα δώσουμε στον στην αρχική κορυφή τον μάιο να είναι μικρότερη από την αρίθμηση που θα δώσουν την τελική κορυφή τον τζέι δηλαδή τη ρύθμιση πρέπει να γίνει με τέτοιο τρόπο ώστε οι ακμές να κατευθύνονται από κορυφές με μικρότερο νούμερο σε μεγαλύτερο νούμερο το καταλαβαίνουμε αυτό θέσεις θα κάνουμε ένα παράδειγμα να εξηγήσω ένα ρύθμιση αρίθμηση με φυσικούς αριθμούς από το ένα έως το πλήθος των κορυφών του γράφημα τόσο fab FIVE είναι οι εξής χώρα δηλαδή αν παρατηρήσετε οποιαδήποτε ακμή στο γράφημα a b BC DLC πηγαίνει από κορυφή που έχει μικρότερη αρίθμηση μικρότερο νούμερο σε κορυφή που έχει μεγαλύτερο νούμερο καταλαβαίνουμε λοιπόν την τοπολογία διάταξη ωραία και φυσικά αυτό που θα μας απασχολήσει σήμερα το πώς βρίσκουμε μια τέτοια διάταξη ένα γράφημα διαπράξει ίσως και πολύ λιγότερες εφαρμογές εστίασε ποιότητας είναι κάποιος που δεν καταλαβαίνει τον ορισμό γιατί είναι πολύ σημαντικό για τη συνέχεια του μαθήματος αν χρειάζεται να το επαναλάβω στο συγκεκριμένο παράδειγμα αυτονόητο να ένα τοπολογία διάταξη αυτό το γράφημα έχει την ίδια απεικόνισης στο επίπεδο του αριστερά με το αρχικό απλώς κορυφή b τώρα έχει αρίθμηση τρεις την ονομάσαμε λυτρωτικό φυλλικό οξύ έχει ρυθμίσει πέντε η κορυφή b έχει αρίθμηση ένα και ούτω καθεξής κεντροδεξιά είναι ένα απαλή απεικόνιση του ίδιου γράφημα τος η οποία έχει σημασία την οποία θα σας εξηγήσω γιατί γιατί βλέπετε έχουμε τις ίδιες κορυφαίας μόνο που τώρα τις διατάσσουν με με βάση την ρύθμιση τους από την πρώτη έως την τελευταία από την 1η έως την 7η στο συγκεκριμένο παράδειγμα και μετά λέμε υπάρχει ένα ακόμη από την κορυφή V4 στην T5 ένα και από την Μ4 στην πέντε υπάρχει κορυφή από την βία ένα στην T5 για παράδειγμα από τη βία ένα στην συγνώμη στην β πέντε και ούτω καθεξής βάζουν δηλαδή τις ακμές που όμως αρχικό γράφημα και σε αυτό εδώ απλώς αλλάζει απεικόνισης στο επίπεδο γράφημα τους και όπως βλέπετε κι αυτό είναι μια πολύ ωραία διαισθητική ιδιότητα και γι' αυτό λέγεται και διάταξη τόπο λογική διάταξη της διατάσσονται απολογητικά από την μικρότερη σε ρυθμίσεις προς την μεγαλύτερη και παρατηρήστε ότι όλες οι ακμές επίζηλο τουρισμού πηγαίνουν από μικρότερα νούμερα προς μεγαλύτερα εδώ θα πηγαίνουν από διαδοχικές κορυφές σαν αριστερά τελικές κορυφές θα είναι δεξιά δηλαδή όλες έχουν φορά από τα αριστερά προς τα δεξιά ακμές λένε αν υπάρχει κάτι που δεν είναι κατανοητό παρακαλώ πείτε μου βεβαίως η συνάδελφος ρωτάει αν αυτό μπορεί να το κάνουμε για κάθε γράφημα περίμενε απάντησε και σε λίγο τώρα λοιπόν το θέμα λοιπόν πως βρίσκουν τώρα αυτό ακριβώς που ρωτάμε έχουν όλα τα κατευθυνόμενα γραφήματα τοπολογία διάταξη μπορεί κάποιος να μου πει νέοι όχι γιατί αυτή παραμένει μια ιδιότητα που χαρακτηρίζει τα κατευθυνόμενα γραφήματα νέο αλλά να σε παρακαλέσω να τις κοντύτερα γιατί δεν θα έχουμε και τι πειράζει εδώ είδαμε αυτό εδώ είχε πολιτική διάταξη παρά γράφει όχι πρέπει κάπως να το πω αυτό που λέω στο αδελφό σας μπορεί να υπάρχει αν η αντίθετη κατεύθυνση είναι κάπως πρέπει να ποσοτικοποιήσει αυτό με γραφείου πολύ σωστά λέει συνάδελφός σου ότι αν υπάρχει κύκλος σε ένα κατευθυνόμενο γράφημα και γιαυτό τον λόγο έχουν βάλει αυτό το πράγμα εδώ ζητούμενο δεν μπορούμε να βρούμε το απολογητική διάταξη και ο λόγος είναι ο εξής κοίταξα το βράδυ κυρίως περί μου πείτε μου ότι εδώ ξεκινώ με κάποιο νούμερο δεν έχει σημασία που ξεκινά με το νούμερο ένα θα πρέπει η κορυφή να πάρει κάποια ρύθμιση μεγαλύτερη της μονάδας για την κομοτηνή τροπολογία διάταξης σημαίνει ότι οι κορυφαίες κατευθύνονται από μικρότερα και μεγαλύτερα νούμερα και επιδοτεί εδώ βάζουμε νούμερο δύο έτσι αριθμούσε δύο εδώ τώρα φραπέ στην κορυφή b για να ισχύσει τοπολογία διάταξη να βάλουμε κάποιο νούμερο που να είναι μεγαλύτερο του δύο έτσι ώστε η ακμή a b να κατευθύνεται από μικρότερο στο μεγαλύτερο νούμερο και συγχρόνως κάποιο νούμερο μικρότερο της μονάδας έτσι ώστε η ακμή σε να πηγαίνει από νούμερο μικρότερο σε μεγαλύτερο το καταλαβαίνουμε και για να μη σας μπερδεύει το κάπνισμα από το μηδέν το 2003 δεν έχει σημασία και εδώ πέντε πάλι το ίδιο πρόβλημα υπάρχει δηλαδή θα πρέπει το b να πάρει ένα νούμερο το οποίο είναι μεγαλύτερο του πέντε αυτό μας λέει δύο η τροπολογία διάταξης και συγχρόνως επειδή πρέπει να ισχύσει και για την ακμή BC το νούμερο που θα πάρει το Ντυνάν μικρότερο του τρεις υπάρχει αριθμός που είναι ταυτόχρονα μικρότερες των τρεις και μεγάλωσε πέντε όχι για το για το λόγο αυτό στα γραφήματα τα κατευθυνόμενα γραφήματα που έχουν κύκλο δεν έχουν τόπο λογική διάταξη δεν κατανοεί το παραπάνω κύκλος μας εμποδίζει να βρούμε αρίθμηση για τουλάχιστον ένα κορυφή που άνοιξε τον κύκλο για το λόγο που σας ανέφερε δεν υπάρχει δηλαδή τέτοια ρύθμιση επομένως απαντήσαμε στην ερώτηση για το ποιά γραφήματα έχουν τοπολογία διάταξη και είναι τα κατευθυνόμενα Articles γραφήματα Ινταλγκό όπως λέγεται στα αγγλικά από τα αρχικά του Direct το PSI κλειδί γράφω και του ένα δάνειο είναι ένα κατευθυνόμενο γράφημα το οποίο δεν περιέχει κύκλους και αυτό που θα αποδείξουμε στη συνέχεια του μαθήματος ναι είναι το θεώρημα όπου αναγράφεται στη διαφάνεια ότι ένα κατευθυνόμενο γράφημα έχει τον πόντο τοπολογία διάταξη αν και μόνο αν είναι δε βρέχει κύκλους διατείνονταν είναι κατευθυνόμενο κεντρικό γράφημα αυτή είναι ιδιότητα που είχε αυτό το γράφημα για παράδειγμα το οποίο στο οποίο βρήκαμε τον Βορίδη διατάξεις δεν τώρα εφαρμογές τι πιο σύνηθες εφαρμογή τον κατευθυνόμενο κυκλικών γραφημάτων καθώς και τις τοπολογία διατάξεις είναι η μοντελοποίηση περιορισμών προτεραιότητας μεταξύ εργασιών που πρέπει να εκτελεστούν δηλαδή όταν οι κορυφές αναπαριστούν διεργασίας έστω σε ένα λειτουργικό σύστημα σε ένα απολύτως εργαστεί οικοσύστημα τότε όταν υπάρχει αξιώνει από την κορυφή διαρκεί στην κορυφή VGA σημαίνει ότι διεργασία φυλάει πρέπει να προηγηθεί της εκτέλεσης εργασίας DJ γιατί γιατί δεν μπορεί να χρειάζεται σαν είσοδο την έξοδο της διεργασίας βία αυτού έχει επίσης αρκετές εφαρμογές αν θέλετε να φτιάξετε το γράφημα των προαπαιτούμενων μαθημάτων δηλαδή πιο μάθημα πρέπει να διδαχθεί πριν από κάποιο άλλο έχει εφαρμογής τους μετάλλιο της Στερεάς πιο κομματικό δικά πρέπει να μετακινούνται στη πριν από κάποιο άλλο για διοχέτευση υπολογιστικών εργασιών όπως σας είπα όπως επίσης και οι υπολογισμοί μου παραστάσεων αυτό το είδαμε σε προηγούμενο μάθημα που ουσιαστικά φτιάχνει ένα κατευθυνόμενο και γλυκό γράφημα και υπολογίζω της παραστατικά υπολογίζω τις πράξεις μετά εντέλεια τους και τις παρενθέσεις τους έτσι ώστε να προκύψει το τελικό αποτέλεσμα και ξέρω πολύ καλά ότι για να γίνει αυτό εδώ πολλαπλασιασμός θα πρέπει να δούμε το αποτέλεσμα αυτής της πρόθεσης και εκείνης το κείμενο της πολλαπλάσιας να όχι πλήρως εδώ για τις εφαρμογές λοιπόν πάμε να δούμε τώρα την πρώτη ιδιότητα ότι κανένα γράφημα έχει τόπο λογική διάταξη τότε το γράφημα είναι κατευθυνόμενο και γλυκό τώρα δεν περιέχει κύκλο δηλαδή αυτό σημαίνει ήταν και η απόδειξη θα γίνει με την μέθοδο της ισότοπο απαγωγής δηλαδή θα υποθέσουμε φωτεινά εδώ φορολογική διάταξη από την κορυφή V1 στην κορυφή δίνει και έστω ότι υπάρχει ένα κατευθυνόμενος κύκλος μπλε κύκλος στο σχήμα αυτό βλέπετε από την κορυφη δύο ΑΕΙ έως την κορυφή VGA και πάλι πίσω που έχουν τι θα συμβεί τι συμβαίνει εδώ μάλλον τώρα προσέξτε έστω διαρρέει ο κόμβος με τον μικρότερο δείκτη ο κύκλος περιλαμβάνει τις κορυφές επαναλαμβάνω VIP έως VGA κάποια κορυφή στον κύκλο είναι εκείνοι που το μικρότερο δείκτη έστω ότι είναι διαγραφή κορυφή κουρέα και όταν κοίταξε τον κύκλο θα υπάρχει επτά επειδή είναι κύκλος θα υπάρχει ένα ακόμη που προηγείται κατά τη φορά του κύκλου της ΡΑΕ αυτή είναι η ακμή δεν είναι βία η οποία κλείνει τον κύκλο EDI δεν έχει άλλη ακμή που ανήκει στον κύκλο και να εισηγμένης ερχόμενη δύσκολη χρυσού 3E τώρα τώρα από την επιλογή του εξαιρούνται των φοιτητών ΑΕΙ είναι μικρότερος δείτε στον κύκλο των ΑΕΙ είναι μικρότερο τονίζει το ξέρουμε αυτό για το οποίο εξάλλου από την άλλη πλευρά επειδή το γράφημα έχει τόπο λογική διάταξη και υπάρχει η ΚΝΕ VGA DVI θα πρέπει και τον τζέι να είναι μικρότερο του ΑΕΙ σύμφωνα με την με τον ορισμό του τοπολογία διατάξεις για την υποδούλωση ακούμε κατευθύνονται εφόσον πράγματι το απολογητικό ταξί από κορυφή με μικρότερο νούμερο όσο μεγαλύτερο νούμερο αυτό όμως τα δύο έρχονται σε αντίφαση κομμένους οδηγούμαστε σε άτοπο άρα το γράφημα μας δεν μπορεί να έχει κατευθυνόμενο κύκλο συναντώνται ξανά από δεν κατάλαβα την απόδοση λοιπόν επαναλαμβάνω άλλη μια φορά προκειμένου να γίνει σε όλους και ειδικά στα παιδιά είχε κατανοηθεί υποθέτουμε ότι το γράφημα έχει ένα κατευθυνόμενο κύκλο έστω από την κορυφή ΒΙΑΛ στην κορυφή VGA περιλαμβάνει όλες αυτές τις κορυφές μάλλον όχι όλα σύννομη αυτό δουλεύει παίρνουμε κοιτάμε και κορυφές ανήκουν στον κύκλο ένα από αυτές θα έχει μικρότερο δείκτη σύμφωνα με τροπολογία διάταξης που υποτίθεται ότι το γράφημα αυτό ένα στο VIP αυτή κορυφή τη μοναδική αιχμή του κύκλου Black μυωπία εισέρχεται στην κορυφή διαρρέει κοιτάμε το άλλο αγρότες το οποίο είναι το VGA επειδή αυτή η αγνή ανήκει στο στον κύκλο και ανήκε στο γράφημα και το γράφημα τοπολογία διάταξη θα πρέπει ο δείκτης σύντομη θα πρέπει ο δείκτης DJ να είναι μικρότερος του δείκτη ice από την άλλη πλευρά επειδή η ακμή VGA am επειδή συγνώμη γιατί επιλέξαμε τον κόμβο αγίου να είναι μικρότερος από καρκίνους στο μπλε κύκλο προφανώς και το αειθαλές δέντρο του ζει επομένως δεν μπορούμε ταυτόχρονα να έχουμε και πρόεδρο του τζέι τζέι μεγαλύτερο του I οδηγούμαστε σε ΝΑΤΟ χώρα τονίζει δεν μπορεί να έχει κύκλο έχουμε δύο ερωτήματα που μένει να δούμε πρώτον αν κάθε κατευθυνόμενο κυκλικό γράφημα έχει τοπολογία διάταξη είπαμε ότι αυτά που έχουν κύκλο δεν έχουν φορολογική διάταξη άρα το ερώτημα είναι αυτά που δεν έχουν κύκλο έχουν όλα τοπολογία διατάξεις και δεύτερον προφανώς πως υπολογίζουμε μια τέτοια διάταξη πάμε πρώτα για να απαντήσουμε στα ερωτήματα αυτά χρειαζόμαστε άλλη μια ιδιότητα που λέει το εξής ότι αν έχουμε ένα κατευθυνόμενο αντίδικο γράφημα τότε το γράφημα αυτό έχει ένα κόμβο χωρίς εισερχόμενο σακούλες ένα τουλάχιστον πέντε , και πάλι απόδειξη θα γίνει με την είσοδο από απαγωγή του λοιπόν υποθέτουμε ότι το ότι έχουμε ένα κατευθυνόμενο και γλυκό γράφημα και ότι κάθε κόμβος υποθέτουμε ότι έχει ένα τουλάχιστον εισερχόμενη ακόμη τι κάνουμε θέλουμε ένα τέτοιο κόβουν άκου όμως το δύο στο σχήμα και ακούω όλοι κινούμαστε οπισθοδρομεί δηλαδή αντίθετα με την κατεύθυνση των ατμο και πηγαίνουμε στήνει σε μια κορυφή q διαπερνώντας διατρέχοντας μπει στο δρόμο την ακμή Αιγίου είχε δείξει γνώμη προέβη και επαναλαμβάνουν το ίδιο από την κορυφή χίου αφού αυτός είναι ένα κόμβος του γράφημα τος υπάρχει τουλάχιστον μια εισερχόμενη ακμή τότε θα πάμε όπου στο δρόμο σε κάποιο άλλη κορυφή π.χ. μέσω διατρέχοντας προς τα πίσω την ακμή π.χ. you όταν το κάνουμε αυτό μοιραία κάποια στιγμή θα συναντήσουμε ένα κόμβο δύο φορές θα επαναλάβουμε κάποια κορυφή γιατί πάντα μπορούμε να συνεχίζουν προς τα πίσω κάποια στιγμή θα εξαντλήσουμε το γράφημα πορεία παρά θα συναντήσουμε κάποια κορυφή SW τουλάχιστον δύο φορές και τώρα εάν λοιπόν το την ακολουθία των κορυφών μεταξύ των δύο επισκέψεων του νταμπλ τιμή αφορά δηλαδή ερχόμενος προς τα πίσω από την κορυφή μέσω των όχι κλπ βρίσκονται w και μετά ακολουθώντας οπισθοδρομεί μα ξανασυναντήσει VW αυτό αυτή διαδρομή μεταξύ των δύο συνεχόμενων επισκέψεων στυλ σε ένα κορυφαίοι την ίδια κορυφή w είναι όπως βλέπετε και από το σχήμα ένα κύκλος που είναι επομένως που σημαίνει ότι το γράφημα μας έχει κύκλο αυτό είναι άτοπο με την υπόθεση το γράφημα μας είναι ακέφαλο επαναλαμβάνονται την απόδειξη θέλουμε να αποδείξουμε ότι αν το γράφημα έχει κύκλο τότε έχει έναν κόμβο τουλάχιστον ακόμα που δεν έχεις ακόμα site τιμές πώς το κάνουμε αυτό λέμε ότι έσω ότι πολιτικών ούτε ότι κάθε κόμβος έχουν τουλάχιστον κάθε κόμπος έχει τουλάχιστον ένα εισερχόμενη ακμή ξεκινάμε από κάποιον κι αυθαίρετα τυχαίο κόμβο και πηγαίνουμε προς τα πίσω δηλαδή διατρέχοντας οπισθοδρομεί τις ερχόμενες ημέρες κάποια στιγμή επειδή όλες οι κορυφαίας ολικού UV έχουν εισερχόμενες έχουμε ας θα επαναλάβουμε μια κορυφή στο τάβλι μα αν κοιτάξουμε τη διαδρομή μεταξύ των δύο πάνελ λήψεων παρατήσει τη σχολή χρήσης τότε αυτή τη διαδρομή προφανώς είναι κύκλος αφού αρχίζει από την κορυφή τζαμί και καταλήγεις στην κορυφή tablet επομένως το γραφείο μας έχει κύκλο το οποίο ένα άτομο στην υπόθεση μας ότι το γράφημα μας ένα κατευθυνόμενο τη δικογραφία αυτή είναι μια πάρα πολύ σημαντική ιδιότητα ουδείς κατευθυνόμενα στα κάτι λίγα γραφήματα μπορεί να βρούμε τουλάχιστον ένα κορυφή με βαθμό εισόδου 0 αυτό σημαίνει διαφορετικά αυτήν γιατί πάνω σε αυτή την ιδιότητα θα χτίσουμε τον αλγόριθμο μας ναι παρακαλώ όχι λένε αυτό θέλουν να αποδείξουν λέμε αυτή είναι υπόθεση μας αν το γράφημα μας είναι κατευθυνόμενο και την υπογραφή μας θέλουμε να αποδείξουμε ότι το γράφημα αυτό έχει τουλάχιστον ένα κορυφή χωρίσεις ερχόμενος αιχμές διαφορετικά όχι δεν λέω αυτό το πράγμα που λέει ότι έχει ένα κόμβο χωρίς επομένως θα μας εδώ για παράδειγμα αυτό ένα κατευθυνόμενο και λίγο γραφήματα έχει κύκλο υπάρχει ένα κορυφή δυνατή η κορυφή δίνει η οποία δεν έχεις επομένως έχουμε το βλέπεις εμείς θέλουμε αυτό το κόστος να παράδειγμα θέλουμε να αποδείξουμε ότι ισχύει για κάθε κατευθυνόμενο κεντρικό γράφημα ότι υπάρχει τουλάχιστον μια κορυφή που δεν έχει εισερχόμενη σακούλας και λέω τουλάχιστον γιατί για παράδειγμα θα μπορούσαν να έχουν κι άλλη ένα κορυφή εδώ στο γράφημα όμως στην κορυφή έχει χώρα καπνός 12 σωστή αυτή ρύθμιση δηλαδή θα πρέπει να γίνει πέντε ας πούμε κι αυτό εδώ που φτάσαμε να διορθωθεί διαρρύθμιση αλλά σε ένα κατευθυνόμενο γραφήματα κυκλικό στη γενική περίπτωση μπορεί να έχω περισσότερες από ένα κορυφαίας χωρίς ερχόμενος έχουμε δηλαδή με βαθμό είσοδο 0 και αυτό που δείξαμε την είσοδο πολιτών φωτιά στο ότι κάθε κόμπος έχει τουλάχιστον ένα επόμενη έχουμε και οδηγηθήκαμε σε αυτό υπάρχει κάποια άλλη ερώτηση βεβαίως διότι πηγαίνοντας πότε θα μπορούσα να συνεχίσω ξεκίνησα από ένα κορυφή και διατρέχει οπισθοδρομεί δηλαδή αντίθετα τις ερχόμενες άγνωστο πότε θα μπορούσε να συνεχίσει ναι δηλαδή πηγαίνει προς τα πίσω εδώ γιατί θα μπορούσε κατ' αρχήν να προχωρήσεις για παράδειγμα κάποια εισερχόμενη μα εδώ έχουμε υπόθεση ότι όλες έχουν μια ακόμα επομένως στην καλύτερη περίπτωση θα εξαντλήσει πρώτα όλες τις κορυφαίες και θα έχουν δουλειά αν ναι ας πουλάει έτσι μια φορά ακριβώς και θα αναγκαστικά αφού η τελευταία έχει νέες ερχόμενη θα επιστρέψεις σε κάποια εποχή CVT έτσι δεν μου αυτολεξεί αυτή απόδειξη πρόγραμμα κατανοητό παιδιά πολύωρα τώρα πάμε να αποτρέψουμε το αντίστροφο της βλήματος ενα που είχαμε πει ότι αν το γράφημα ήταν εκεί το ποντίκι διάταξη αποδείξαμε ότι το γράφημα είναι κυκλικού όταν θα πάμε να αποδείξουμε πάντες το αντίθετο το αντίστροφο δηλαδή εάν το ρύζι είναι κυκλικό τότε τονίζει έχει τοπολογία διάταξη δηλαδή όλα τα τοπολογία τα κατευθυνόμενα κυκλικά γραφήματα έχουν τοπολογία διάταξη ήταν η δεύτερη ερώτηση που δεν μου που θέλαμε να απαντήσουμε αυτήν την απόδειξη προσέξτε είναι με υπαγωγή τους το πλήθος των κορυφών του γράφει πάντως πολλά λοιπόν πάμε να δούμε τη βάση εισαγωγής έχουμε το τετριμμένο γράφαμε μια κορυφή και καθόλου πλευρές προφανώς αυτό 1000 πολιτική διάταξη έτσι που αρνείσαι την ένα ένα κόμπους επομένως η βάση εισαγωγής ισχυρή τώρα ξέρουμε από το την προηγούμενη ιδιότητά ότι όταν έχουμε ένα κατευθυνόμενο κυκλικό γράφημα με περισσότερες από ένα κορυφαίας τότε μπορούμε να βρούμε ένα ακόμη φόβοι στο γράφημα του όποιος δεν έχεις επομένως έχουμε δηλαδή αυτό της ουκρανίας διατυπωμένες δεν υπάρχουν ακόμα σακούλας το γνωρίζουμε από το λήμμα που μόλις αποδείξαμε φορέων τι κάνουμε στην περίπτωση αυτή βρίσκουμε ένα τέτοιο Κονγκό ΔΕΗ και το αφαιρούμε από το αρχικό γράφημα φορέων όταν αφαίρεσε ένα κόμβο γεύσεις από το γράφημα αυτό το οποίο δεν έχει ακόμα πάντως δεν έχει εισερχόμενες ακούμε η διαγραφή αυτή δεν μπορεί να δημιουργήσει κύκλο στο γράφημα της δεν είναι επομένως το γράφημα αυτό δηλαδή των ζημιών την κορυφή την οφειλή για την οποία αφαίρεσαν είναι επίσης ένα κατευθυνόμενο αγγλικό γράφημα τώρα όμως έχω ένα γράφημα που έχει ένα κορυφή λιγότερη από το αρχικό παρά σε αυτήν μπορώ να εφαρμόσω την επαγωγική υπόθεση δηλαδή ξέρω λοιπόν ότι το γράφημα που μένει αυτό το γκρίζο σύννεφο εδώ μετά την αφαίρεση της κορυφής v έχει τοπολογία διάταξη πολλά όταν όμως καρό τώρα θέλω λοιπόν των ΔΕΗ το οποίο δεν έχεις ερχόμενες αγνές και το ποτό το πρώτο στην υπολογιστική διάταξη και μετά ακολουθεί η πολιτική διάταξη τον ατμό των ζημιών δεν αφού δεν έχεις ερχόμενος ακμές και το έχω τοποθετήσει πρώτος απολογήθηκε διάταξη θάχει το μικρότερο νούμερο και άρα οι κορυφές των ΑΜΚ οι τελικές κορυφές των εξερχόμενων πλευρών του θα έχουν οπωσδήποτε κάποιο νούμερο μεγαλύτερο από αυτό που έχει κόβει ρε ξαναλεω την απόδειξη μου φαίνονται μπόρεσε δεν η οποία επαναλαμβάνω έχει με το υπόλοιπο γράφημα τζέι έχει μόνο εξερχόμενες έχουμε δεν υπάρχουν εισερχόμενος στο δη παραλαμβάνω ότι έχω την κορυφή ΔΕΗ η οποία δεν έχεις ερχόμενος προσούτο και αυτό το έχω αφαιρέσει από το γράφημα μου εδώ βρίσκω ένα πολιτική διάταξη ωραία η τροπολογία αυτή διάταξη πείτε ότι είναι ένα αξιόλογο δίνει κάποιες στιγμές πέντε 15 κλπ στα στις κορυφές του Γράμμος πιασμένο το γράφημα τους αυτό που κάνω είναι αφήνονται υπόλογοι διάταξη αυτή ως έχει και λέει ότι το VR έχει πολεμική διάταξη 0 κ ξεκινάω να ρυθμίσουμε από το η αν θέλετε μετά το κάνω αυτό είναι και πολύ στενό προς τα δεξιά κατά ένα πρόσθετο σε όλα γραφημάτων τζέι τις κορυφές κατά 9 αυξάνουν το το δεχτεί την ετικέτα που δεν το πόλο και διάθεση διάταξης νόμου επομένως από εδώ λοιπόν εφόσον επιδοτεί βάλε στο v το νούμερο 0 όλα τα άλλα έχουν νούμερο μεγαλύτερο αυστηρά του μηδενός επομένως όλες οι εξερχόμενες αιχμές από το ότι θα ικανοποιούν την ιδιότητα της τοπολογία διατάξεις επομένως το γράφημα μου έχει και ο πολύ γράφει μου έχει και πολιτική διάταξη αυτή είναι ένα απόδειξη με καταγωγή ξεκινήσαμε δηλαδή από το βήμα από το τριμμένο γράφημα από το βήμα της επαγωγής γέννησαν ένα υποθέταμε ότι ισχύει επαγωγική υπόθεση για οποιοδήποτε γράφημα με λιγότερες από 20 θες είπαμε να κάνουμε το παραγωγικό βήμα για να το κάνουμε αυτό που κάνουμε κάτι πάρα πολύ απλό για μένα το γράφημα παρόμοια κορυφή που έχει βαθμό εισόδου 0 που ξέρω με βεβαιότητα από την προηγούμενη απόδειξη την προηγούμενη ιδιότητά της ότι υπάρχει την αφαιρώ βρίσκονται πολεμική διάταξη με βάση την παραγωγή υπόθεση στο υπόλοιπο γράφημα και μετά προς τα έξω τη βίαιη και προσόντων ρύθμιση 09 παρά που είναι κάτι μικρότερο από οποιαδήποτε αρίθμηση έχει πάρεδρος τίποτε κόμβος στο γράφημα το υπόλοιπο που μένει μετά την αφαίρεση του δη κι αυτόν μια έγκυρη τοπολογία διάταξη όλο το γραφείο χώρα επομένως αποδείξαμε το θεώρημα που θέλαμε να που σας είπα στην αρχή ότι ένα κατευθυνόμενο γράφημα το φορολογική διάταξη αν και μόνο αν τώρα είναι ένα κατευθυνόμενο την υπογραφή τους κι αφού έχουμε συζητήσει όλες αυτές τις ΑΜΚ ιδιότητες πάμε να δούμε ένα ανάλογου αριθμού εύρεσης τόπο λογικής διάταξης αναγραφή μόνο αυτός αλγόριθμος που βάσκο βασίζεται στη δεύτερη ιδιότητα ότι δηλαδή κάθε κατευθυνόμενο αρχιτεκτονικό γραφείο μάχη τουλάχιστον ένα κορυφή βαθμού εισόδου 0 και επίσης κάντε κάτι άλλο γιατί εμάς δεν μας θέλουν μονάχα να ζούμε εάν τα δεδομένα ένα κυκλικού γραφημάτων βρασμού τοπολογία διάταξη θέλουμε κάτι παραπάνω θέλουμε θέλαμε ο σάλιβαν δηλαδή ούτι δεδομένου οποιουδήποτε γράφημα εντός αν το γράφημα αυτό έχει τοπολογία διάταξη όχι και αν ναι υπολόγισαν αυτήν τοπολογία διατάξεις φορέων ο αλγόριθμος αυτός είναι ο εξής ξεκινάει και με την ώρα με τον υπολογισμό των εισερχομένων ατόμων σε όλους τους κόμβους τον βαθμό εισόδου λέει ξανά σε υπάρχει κορυφή με βαθμό εισόδου ήταν εάν δεν υπάρχει δηλαδή αν όλες οι κορυφαίες έχουν από μέσα μας τότε ξέρουμε από το λήμμα δύο ότι υπάρχει κύκλος σταματάμε αλλιώς είμαστε Σ'αυτή την περίπτωση κάτω βλέπετε δεν υπάρχει βαθμός δεν υπάρχει κορυφή που έχει βαθμό εσόδων 0 του όλες οι κορυφές έχουνε ένα εισερχόμενη ακμή είναι εάν λοιπόν υπάρχει τότε παίρνουμε ένα μια τέτοια κορυφή βαθμός 0 και τη βάζουμε πρώτη την αρίθμηση και μετά διαγράφουμε την κορυφή αυτή και τις εξερχόμενες ακούμε στις και επαναλαμβάνουμε τη διαδικασία τέλος στο γράφημα δηλαδή που απομένει ένα κορυφή με βαθμό εισόδου 0 ωραία λέμε ότι αυτή έχει αρίθμηση ένα την προηγούμενη δύο για παράδειγμα αφού δώσαμε ένα στην προηγούμενη αφαιρούμε την κορυφή αυτή και τις εξερχόμενες έχουμε αίσθηση της διαγράφουμε το γράφημα και επαναλαμβάνουμε τη διαδικασία δύο πράγματα θα συμβούν είτε θα εξαντλήσουμε το γράφημα αφού διαγράφουμε κορυφές και ακμές είτε θα υπάρχει ένα σημείο στο οποίο θα μπορούν να προχωρήσουν γιατί γιατί έχουμε φτάσει σε ένα υπογραφή μα το γράφημα τος μετά από τις αλλεπάλληλες διαγραφές κόμβων και ακριβών στο οποίο δεν θα υπάρχει κορυφή με βαθμό εισόδου 0 δηλαδή εδώ δε θα μπορεί να βρεθεί αυτός κόμβος είναι για να τον για να υπολογίσουν για αυτούς για να συνεχίσουμε την αρίθμηση μας που θα μας δώσει τελική πολιτική διάταξη αυτό τι σημαίνει από το από το έλλειμμα του δύο ότι αυτό το υπογράφει μα έχει κύκλο αφού υπογραφεί μα όλες οι κορυφαίες έχουν βαθμό εισόδου τουλάχιστον ένα αφού λοιπόν το υπογράφει μαγική του προφανώς και το αρχικό γράφημα έχει κύκλο είναι αυτός ο ρυθμός επαναλαμβάνω κάνει δύο πράγματα μας λέει δεδομένου του αθλήματος το πράγμα έχει και πολιτική διάταξη κι αν όντως έχει την υπολογίζει άλλος λέει ότι το γράφημα έχει κύκλο και επομένως δεν έχει τόπο λογική διάταξη με όχι βέβαια ούτε καν για παράδειγμα να κανένα παράδειγμα εκτελεστό αλγορίθμου στο αρχικό μας παράδειγμα και μετά θα κάνω ένα παράδειγμα αυτό που για αυτό που ρωτάς στο ποτέ αλγόριθμος σταματάει μισό λεπτό γι να καταλάβετε λίγο την εκτέλεση του αλγόριθμου πάμε να δούμε να αυτό εδώ είναι το αρχικό γράφημα τηλέ αλγόριθμος κοίταξε να βρεις κορυφές που δεν έχουν επομένως έχουμε ας μπορείτε να βρείτε μια τέτοια ακολουθεί να email μηνύει την κορυφή ώρας οποιαδήποτε μας κάνει αυτή λοιπόν τη Γάλλο της δίνω αρίθμηση ένα και την αφαιρώ από το γράφημα αυτήν και τις εξερχόμενες ακούμε στις μένει το υπογράφει σήμερα της που είναι η κορυφαία σου έχουν με σημειωμένα με μπλε χρώμα και οι ακμές που δεν είναι διατυπωμένες έχουμε τώρα ρωτάω υπάρχει ένα κορυφή από τις μπλε η οποία έχει βαθμό εισόδου 0 δηλαδή δεν έχεις ακόμα site μας MBA master επτά πρώην ώρα αυτή έχει θα πάρει μόνο δύο ανθρωπολόγοι διάταξη και αφαιρούμε αυτή την κορυφή μαζί με τις παρά τις εξερχόμενες έχουμε στις και το γράφω τις κορυφές τροπολογία διάταξης θα τώρα μπορείτε να μου πείτε από τις βλακώδεις θέσεις ποιά είναι εκείνη που έχει βαθμό εισόδου 0 με ίσοι γιατί αυτήν την έχουμε διαγράψει έχει λοιπόν θα πάρει λοιπόν ακολουθήσει αριθμό τρεις θα διαγράψουμε την κόρη φυσικά τις εξερχόμενες ακούμε στις και επαναλαμβάνουμε τη διαδικασία η επόμενη θα είναι η κορυφή αντί η οποία θα πάρει δώρο τέσσερις στην πολωνική διάταξη και θα διαγράψουμε την κορυφή αυτή μαζί με την ένα εξερχόμενη ακμή της οι επόμενοι κορυφή που δεν έχει από τις τρεις μπλε τώρα που δεν έχει έχει βαθμό εσόδων δεν είναι κορυφή γι που θα πάρει το ποντίκι αρίθμηση πέντε διαγράφουμε αυτήν και τις διώξω κομμένες ακούμε στις έμειναν δύο κορυφές η ΕΥΠ έχει βαθμό εσόδων δεν μου αυτή θα είναι η έκτη και διαγράφουμε αυτήν και την εξερχόμενη ακμή της και τελευταία μένει κορυφή τζιπ δεν έχει καθόλου ακούμε σκαθάρι τελευταία κορυφή σε τόπο λογική διάταξη έτσι δουλεύει αλγόριθμος εφόσον υπάρχει πολιτική διάταξη είναι οκ ναι δεν είναι αυθαίρετη λέω συνεχώς ότι θα μπορούσαμε τις κορυφές εδώ στην αρχή τέθηκε Μπιναλί φάρο ναι είναι αυθαίρετη επιλογή μπορεί να πάρεις όποια θέλεις ακούω την ρώτησε πιο συγκρότησε εγώ πολλά τώρα να απαντήσω στην ερώτησή της συναδέλφους ως σχετικά με το τι θα συνέβαινε αν υπήρχε κύκλους κέντρο δεν αναγκάζονται από την αρχή εγώ εφαρμόζω αλγόριθμο ο αλγόριθμος λέει ότι εγώ περνά ένα κορυφή με βαθμό εισόδου 0 τις ενορίες μισή ένα ματιά στη ΔΟΥ κορυφή και διαγράφω και αν θέλετε ένα πιο γενικό το πρώτο παράδειγμα ακόμα θα βάλω και άλλη ένα κορυφή εδώ στην κορυφή της παρά τον νόμοι οποιαδήποτε αυτής δύο πόροι απλώνονται οι κορυφαιοι της δίνω αρίθμηση ένα διαγράφω την κορυφή μαζί με την εξερχόμενη ακμή της θα παραλαμβάνονται διαδικασία θέλω την επόμενη κορυφαίοι νέα βαθμό εισόδου 0 χωρίς επομένως αιχμές της δίνω αρίθμηση δύο διαγράφονται κορυφή αυτή μαζί με τις εξερχόμενες φτάνουμε στις φορέα μετά παίρνω ένα κορυφή με βαθμό εισόδου 0 ποια είναι αυτή είναι κορυφή έχει της Renault αρίθμηση την επόμενη ρύθμιση το τελευταίο δηλαδή που είχα δώσει νούμερο συναντά διαγράφω μαζί με τις εξερχόμενες ακούμε στις μετά παίρνω κορυφαία βαθμός σόδα 0 να είναι χώρες Πέμπτη η οποία τέσσερις διαγράφω αυτήν και τις εξερχόμενες ακούμε στις μετά λέω παίρνω την επόμενη κορυφή με βαθμό εισόδου 0 δεν υπάρχει βούληση και βλέπουμε ότι το κόμμα αυτό το υπογραφή μα έχει ένα κύκλο έτσι ο κόσμος σταματάει σταματάει γιατί εδώ δεν μπορεί να βρει κορυφή με βαθμό εισόδου 0 δε σημαίνει ότι αυτό πρέπει να βρει από την αρχή αν αυτή είναι η ερώτησή σου μου όχι δεν τις ψάχνεις κορυφαίας αλουμινένια πολλές περιοχές όχι αλγόριθμος παιδιά έχω κάνει το εξής ξεκινάει το μόνο που κάνει είναι ότι υπολογίζει βαθμός εισόδου στους οποίους μπορεί να έχει και έτοιμους αν κανείς κάνει την αναπαράσταση σε λίστες γειτνίασης ωραία και από κει και πέρα αυτό που κάνει κάνει αυτή τη διαδικασία ξεκινά είναι ένα κορυφή με βαθμό εισόδου 0 τις 9 ρύθμιση αν δεν υπάρχει τέτοια κορυφή σταματάει αμέσως και λέει ότι αλλά εδώ υπάρχει κυρίως ωραία αλλά μπορεί όπως εδώ μα υπάρχουν εντούτοις ότι είχαν δύο κορυφές με βαθμό ίσως δεν προχώρησαν μέχρι κάποιο σημείο και μετά δεν μπορούμε να προχωρήσουμε γιατί φτάσαμε σαν να υπογράφω Man το οποίο είχε κύκλο αφού υπογραφεί συλλογική προφανώς και το αρχικό γράφουμε κύκλο τώρα καν ναι συμπερίληψη ρωτάει συνάδελφός σας αν θα μας χρειαστεί τοπολογία διάταξη όχι δεν έχει καν το φορολογική διάταξη το γράφημα αυτό με τις τώρα λοιπόν θα συζητήσουν μετά χωρίς φώτα και πολυπλοκότητα του αλγόριθμου μέταλλο το γυαλί η ορθότητά του αλγόριθμου που είδαμε την προηγούμενη ορά βασίζονται στην ιδιότητα του ελλείμματος δύο δηλαδή εάν υπάρχει κορυφαίοι γράφημα μάλλον βίζα θυμηθούμε πολιτογράφηση των δύο είναι αν κατευθύνονταν κυκλικό εάν υπάρχει κόμβος χωρίς ερχόμενες αιχμές ανάποδα αν ένα γράφημα έχει τουλάχιστον κάθε κοσμούσαν γράφημα ζει τουλάχιστον μια εισερχόμενη ακμή το γράφημα κύκλο αυτό ήταν κι αυτοί είναι ουσιαστικά ύλη απόδειξη ορθότητας του αλγόριθμου αυτού εδώ δηλαδή ενόσω δεν υπάρχει να τελειώσω μάλλον κατά τη διάρκεια εκτέλεσης του αλγόριθμου μπορούμε συνεχώς να βρίσκουμε μέχρι εξάλειψη του γραψίματος κορυφές με βαθμό εισόδου 0 τότε αυτό είναι ένα κατευθυνόμενο κυκλικό γράφημα και όπως αποδείξαμε τοπολογία διάταξη την οποία αλγόριθμος βρίσκει ανάποδα αν κάποια στιγμή δεν μπορούμε να προχωρήσουμε γιατί δεν μπορούμε να βρούμε κορυφή με βαθμό εισόδου δεν τότε το γράφημα αυτό έχει κύκλο από το κλίμα δύο τοπίου Αποδείξαμε ωραία πάμε να δούμε τώρα αν τιμή χρονική πολυπλοκότητα του η οποία προβλέπεται ισχυρίζομαι ότι είναι γραμμική στο έτος εισόδου δηλαδή στον αριθμό των ατόμων και των αριθμό των κορυφών του γράφημα ως δεν μπορείτε εσείς να αναπτύξετε έναν αλγόριθμο βουνά σας δίνω εγώ ένα γράφημα να μου πείτε εάν έχει τοπολογία διάταξη και αν έχει κάτι βρείτε και Γράμμου διαγράφονται την είσοδο ασθενή δεν μπορεί να καταστρέφεται την είσοδο άλλωστε βρείτε το πολιτική διάταξη για τι πράγμα βρίσκεται για το διάγραμμα ενώ γράφημα πώς θα μπει πώς θα μπορούσα να το επιλύσουμε αυτό μια βίζα μου έχει κάνεις καμία ιδέα ένα αλυσίδα αντιδράσεων το γράφημα η αντιγραφή όμως δεν είναι λύση όπως αντιγραφή δεν είναι λύση να και για τον εξής λόγο γιατί συνήθως όταν υλοποιείται τις δώρο ένα γράφημα τη δρομέας οι οποίες αποθηκεύουν κόμβους και κορυφές είναι συνήθως τύπου δείκτη μόνωση αντιγραφη μετά μπορεί να έχετε πρόβλημα με μένα μέσα στους δείκτες δηλαδή να βρείτε κάτι για το γράφημα το οποίο έχετε αντιγράψει τώρα για το αντίγραφο αλλά αυτό πρέπει να είστε πολύ προσεκτικοί πώς σχετίζεται με το αρχικό γράφημα είναι πλέον δουλειά γιατί οι δείκτες που θα αναφέρονται στο αντίγραφο δεν έχουν καμία σχέση με το αρχικό γράφημα είναι κατανοητό αυτό ναι υπάρχει ένα δείκτης προς την κορυφή έτσι το αντίγραφο της υπονοούμενο είναι μια διαφορετική θέση μήνυση μια διαφορετική αν θέλεις ομάδα παιδιών δομή λέγεται αυτό σε ένα διαφορετική δομή γραφημάτων στο αντίγραφο της επομένως ότι πληροφορία και για το είδος μου τέτοιο πως σχετίζεται με το αντίγραφο της ΔΕΗ τουλάχιστον μετρημένο τρόπο πρέπει να κάνεις κάτι παραπάνω για αυτό έτσι ώστε να να έχεις ένα προς ένα έσοδο στοιχεία μεταξύ πρωτότυπου και αντιγράφουν όσον αφορά τις κορυφές και τις ακμές θέλει κανείς άλλος κάποια άλλη ιδέα εκτός αντιγραφής καταρχήν ο ένα τρόπος είναι να Σημειώνουμε Κατερίνη διαγραμμένοι της ΝΔ βάζουμε μια ετικέτα ζωντανό διαγραμμένων 01 ένα τόπος αυτός το πρόβλημα όμως είναι ότι όταν εγώ κάνω εδώ τις διαγραφές θα πρέπει να ενημερώνω όπως διαγράφονται τους βαθμούς εισόδου των κορυφών φοβερά επομένως πρέπει κάπως εδώ να κρατάω ένα πληροφορία ποιος είναι βαθμός είσοδο δύσκολη PCB για παράδειγμα της ABB όταν πόδι διαγράφω την ακμή τι λέει πρέπει να φέρω ένα από το βαθμό εισόδου της κορυφής λέει σε αυτήν ιδέα δηλαδή δεν διαγράφω τίποτα τα σημειώνω προς διαγραφή και προσέχω τους βαθμούς εισόδου ουσιαστικά η μοναδική πληροφορία που θέλω εδώ να ξέρω για κάθε κορυφή του γραφημάτων είναι πως μειώνεται βαθμός ισόβια τίποτα αλλά αυτό με ενδιαφέρει όπως τρέχει αλγόριθμος εκτελείται και αυτό κάνω δηλαδή κακάο δύο πληροφορίες το καβούκι του W.E. είναι ουσιαστικά ο αριθμός των εισερχομένων ατόμων του w στην τρέχουσα επανάληψη του αλγόριθμου αρχικά ένα βαθμός εισόδου αλλά πως προχωράει η εκτέλεση του αλγόριθμου αυτού μειώνεται κατά ένα η κατάρα των αριθμών που σημειώνονται προς διαγραφή και μετά να πάω και να σύνολο που ουσιαστικά είναι μια λίστα οι οποίες αιτίου στην όποια λίστα ένθετο της κορυφαίας με βαθμό εισόδου 0 προκειμένου να τις ξέρω ποιος είναι και κάθε φορά θέλω μια τέτοια ακμή από ένα τέτοια κορυφής συγγνώμη από τη λίστα διαγραφή από τη λίστα και σημειώνω προς διαγραφή από το γράφημα αυτήν και τις εξερχόμενες αιχμές ουσιαστικά αυτό δε χρειάζεται καν να το κάνω το μόνο που έχω να κάνω είναι να κοιτάξω ποια είναι αυτή η κορυφή δω βίας με την οποία θα διαγράψω και να πάω στις εξερχόμενες κορυφαίες στα άκρα τους οι τελικές κορυφές και να αφαιρέσω ένα από το βαθμό εισόδου αυτόχειρες θα τίποτε άλλο το ξαναλέω έχω δηλαδή ένα κορυφή εδώ β την οποία εξετάζω την οποία έτσι αυτές τις εξερχόμενες ακμές κ εγώ αυτό που χρειάζεται εδώ να κάνω είναι όταν εξετάζω αυτή την κορυφή να την διαγράψει από τη λίστα των κορυφών με βαθμό εισόδου 0 όχι το γράφημα και να αφαιρέσουν ωραία στενά από τους βαθμούς εισόδου των κορυφών u ένα δύο κ μηδενικές κορυφές των γραμμών των εισαγόμενων από την κορυφή αυτή είναι η σωστή υλοποίηση του αλγόριθμου και έτσι πρέπει να το μετρήσουμε την πολυπλοκότητα του τώρα όσον αφορά την αρχικώς ποίηση μωράκι τόσος χρόνος να σαρώσουν τις λίστες γειτνίασης για να βρουν αρχικά τους βαθμούς εισόδου ωραία πήρε βαθμούς έξω είναι ακριβώς το ίδιο πράγμα αυτό το είδαμε σε προηγούμενό μας τώρα και κάνω όταν έχω ένα κορυφή βίλι που κατά τον αλγόριθμο είναι προς διαγραφή αφαιρώ αυτή την κορυφή v από το σύνολο της ενώ την πρώτη κορυφή τους συνωμότες που είναι ουσιαστικά μια λίστα διαγράφονται τραγικών επί της λίστας αυτό μου παίρνει σταθερό αριθμό πράξουν με το δίκαννο αυτό που σας είπα κοιτάω τις απέναντι κορυφές τις τελικές κορυφές των 6,1 βαθμών της v και αφαιρώ ένα απότοκα των tablets όπου το ταμπλό πριν τώρα τιμές ηχείου ένα year δύο u κ κλπ δηλαδή μουσικά δόκανο ένα βρόχου Σιμόν για όλες τις εξερχόμενες αγνές διήγημα ΑΕΙ πήγαινε στο counter URL και αφαίρεσε ένα αυτή την πράξη που επίσης παίρνει σταθερό χρόνο και εάν βγει κάποια κορυφή κάνοντας εδώ την αφαίρεση παρατήρησε ότι αυτή η κορυφή έχει βαθμό εισόδου 0 οι κανόνες του Νταβέλη γίνει ίσο με το 0 τότε την κορυφή αυτή την ένθετο στη λίστα ένα και επαναλαμβάνω τη διαδικασία μέχρις ότου να διαγραφούν όλες οι κορυφές από τη λίστα της αυτό λοιπόν επαναλαμβάνω τι κάνω επισκέπτομαι κάθε κορυφή και κοιτάω τους βαθμού τις εξερχόμενες ακούμε στις για κάθε εξερχόμενη ακμή ξοδεύω σταθερό χρόνο γιατί αυτό που κάνω είναι ΠΑΟΚ κάνουν τις απέναντι τελικής κορυφής και αφαιρούμενα τα και αν αυτό γίνει δεν με ένα έλεγχος είναι αυτός τότε την ένθετο στη λίστα πες επομένως συνολικά δηλαδή θα μου πάρει το έχουμε ξαναδεί αυτό αλγόριθμους λοιπόν κάνει χρόνου αναλόγως του αριθμού των κορυφών γιατί επισκέπτεται κάθε κορυφή Σελίνου χρόνο ανάλογο των βαθμών εξόδου όλων των κορυφών αυτό όμως ξέρουμε πόσο κάνει έτσι απ το θεώρημα του χωριού επομένως κάνει τον αριθμό των πλευρών όλο λοιπόν αυτό είναι αυτό το άθροισμα που αναφέρει το διατύπωσε το θεώρημα τόσες δηλαδή το πλήθος τον ακριβών και των κορυφών του γράφημα τους επί ένα σταθερά τώρα αλλά ξέρω γω ας το πω άλλη μια φορά τι κάνουμε έχουμε αρχικό ποίηση μ ένα αυγό ένα ένα σύνολο εσύ ένα λίστα πούμε μια σάρωση βλέπουμε πίστεως κορυφές έχουν το κάνουν που συμβολίζει το βαθμό είσοδος από το μηδέν και αυτές να σε δούμε στη λίστα νέα επαναλαμβανόταν κάνουν επίσης μπορούμε να μετρήσουμε από την λίστα γειτνίασης όπως σας είπα είναι πάλι είναι το ίδιο άθροισμα δομών που το κάνουμε για βαθμούς είσοδο ώρα πολυάσχολη αρχικό ποίηση παίρνει γραμμικό χρόνο το ενδιαφέρον έχει από 13 που κάνουμε το εξής έχουμε δύο ετών λειτουργίας τον είναι επισκεπτόμαστε κάθε κορυφή με βαθμό είσοδο 0 που σημαίνει ότι παίρνουμε μια κορυφή από το σύνολό σου πούνε μια λίστα διαγράφουμε και ε γόνιμος και πρέπει να διαγράψουμε και τις εξερχόμενες ακμές ενημερώνοντας τους βαθμούς εισόδου των απέναντι κορυφών αυτό το κάνουμε με έμμεσο τρόπο όχι με άμεσο δηλαδή στην κορυφή δεν την ξεχνάμε από τη λίστα συναντώνται ξανά δούμε ποτέ γιατί μόνο κοιτάμε κορυφές από λίστα αυτό μας φέρνει σταθερό χρόνο γιατί αν χειριζόμαστε αυτή τη λίστα για παράδειγμα σαν ένα αγορά διαγράφουν από την αρχή της ώρας και θέτουμε στο τέλος μας ωραία και κάνουμε κάτι για τις εξερχόμενες ακμές που πρέπει να διαγράψουμε το διαγράφουμε μας αρκεί να πάμε στους δείκτες κάνουν τον απέναντι κορυφών και να αφαιρέσουμε ένα μονάδα αυτό σημαίνει διαγραφή και ενημερώνουν τους δίδασκαν αυτό και μας φέρνει μας παίρνει για κάθε κορυφή τόσο χρόνο αναλόγως του αριθμού των εξερχομένων ατόμων γιατί για κάθε ένα τέτοια εξερχόμενη ακμή εγώ ξοδεύω σταθερό χρόνο αφαιρώ έναν άσο από το κανόνι του νταμπλ και β ότι κάτι άλλο εάν εκείνη την ώρα που αφαιρώ το νάσο κανέναν πλέον ελέγχους κοιτάω εάν το count Down είναι μηδέν που σημαίνει ότι αυτή είναι ένα κορυφή w που ο βαθμός είσοδό τους μειώθηκε στο 0,69 το την κάτω στο τέλος της λίστας πες έχω λοιπόν μια σύγκριση και ένα θέση στο τέλος μιας χώρας που και τα δύο παίρνουν σταθερό χρόνο χώρα επομένως για κάθε ένα ακόμη ισοδύναμο σταθερό χοντρικά και είσπραξης παραπέρα ενώ και ένα άλλος τρόπος για την πολυπλοκότητα ένα επισκέπτομαι κάθε κορυφή ένα αφορά τη βία στην θα την επισκεφθώ ωραία και διαγραφών από τη λίστα σας ρίζα οπότε και μπορώ να δω αυτήν αντί τις εξερχόμενες ακούμε στις πάλι μια φορά στο και ξοδεύω για κάθε ακμή και κάθε κορυφής σταθερό χρόνο επομένως ο χρόνος θα είναι ανάλογος του πλήθους των κορυφών και τον βαθμό του γράφημα τους γραμμικός αλγόριθμος δηλαδή βέλτιστος υπάρχει ένα εναλλακτικός αλγόριθμος εύρεσης τροπολογία διάταξης απλώς στον εαυτό σας το αναφαίρετο για λόγους πληρότητας κι αν ουσιαστικά πάω είναι εφαρμογή της εκτέλεσης της αναζήτησης πρώτα καταβάθος μόνο που εδώ αυτό που κάνουμε είναι ότι η διάταξη προκύπτει από τους χρόνους καταλήψεις πηγαίνοντας από κορυφή με μεγαλύτερο νούμερα ακολούθησε μικρότερο αλλά αυτό δεν υπάρχει θέμα δηλαδή αν έχουμε την τροπολογία διάταξης φθίνουσα σειρά είναι είναι θέμα συμβάσεις είτε ξανά ονοματίζουν ότι θυμίζω ότι κάνουμε αύξουσα δίνουμε νέα ονόματα νέα ρύθμιση είτε χρησιμοποιούμε τη φθίνουσα σειρά αρκεί να έχουμε την ίδια σύμβαση για όλους έχουμε ένα διεθνές πηγαίνουν από κορυφή μεγαλύτερο νούμερο ως κορυφή σε μικρότερο νούμερο και ίσως θα επανέλθουμε σε αυτό τον τόνο τον αλγόριθμο εάν χρειαστεί το ερώτημα είναι τι πώς θα μπορούσε να τροποποιηθεί αυτός ο δήμος έτσι ώστε να δέχεται ως σοβαρά οποιοδήποτε κατευθυνόμενο γράφημα και να βρίσκει το ομολογεί διάταξη άλλος σταματάει δηλώνοντας το δίκυκλο έτσι όπως είναι ο αλγόριθμος γραμμένος δεν μας λέει εάν το γράφημα έχει όντως τοπολογία διατάξεων το γράφω μπορώ και τείνουν να είναι αλγόριθμος αυτούς δουλεύει σωστά εφόσον το είσοδος είναι ένα κατευθυνόμενο κυκλικό γράφημα κανένα γενικό γράφημα πώς θα μπορούσε να τροποποιηθεί από αυτά που έχουμε κάνει μέχρι τώρα για την αναζήτηση πρώτα κατά βάθος να όχι αυτός δεν ελέγχει βάσει όσα βρασμένα έλεγχο πάλι βαθμούς εισοδημάτων πάμε στον προηγούμενο αλγόριθμο σας διαφορετικός διαγωνισμός ο αλγόριθμος αυτός λέει το εξής ότι δεδομένου βεβαίως κατευθυνόμενο τη λιγούρα χρήματος κάνω ένα αναζήτηση πρώτα κατά βάθος και ΕΟΠΠΥ αναζήτησε αυτό μου δίνει χρόνους ανακάλυψης και χρόνους εγκατάλειψης και χρόνια εγκατάλειψης είναι η πολωνική διάταξη η οποία την οποία ζητάμε απλά το ερώτημα είναι πως αυτός αλγόριθμος μπορεί να τροποποιηθεί έτσι ώστε το επόμενο οποιοσδήποτε γραφημάτων ως να σας λέει ναι υπάρχει τοπολογία διάταξη τη γη και να βρίσκει όχι δεν υπάρχει πολύ σωστά πάρα πολύ σωστά θα πρέπει να υπάρχει αν υπάρχουν πίσω τιμές στο γράφημα θυμάστε ότι υπάρχει κατηγοριοποίηση των Mac μορένο κατευθυνόμενη γράφημα τόσο σε ακμές δέντρου πίσω ακμές εμπρός έχουμε σχεδιάσει παιδικές στιγμές ένα κατευθυνόμενο και λίγο γράφημα όπως είπαμε στο προηγούμενο μάθημα δεν έχει πίσω μας εάν λοιπόν ως αποτέλεσμα της αναζήτησής πρώτα καταβάθος στον πρώτο βήμα εσείς παρατηρήσετε ότι υπάρχουν στο γράφημα πίσω μες τότε το γράφημα έχει κύκλων και δεν μπορείτε να βρείτε εδώ φορολογική διάταξη αν δεν υπάρχουν πίσω από νέες συνεχίζοντας τα υπόλοιπα βήματα του αλγόριθμο και ουσιαστικά χρόνια εγκατάλειψης σας δίνουν τον τοπολογία διάταξη πάμε στο δεύτερο πρόβλημα Βασίλη θα συζητήσουμε σήμερα την εύρεση ισχυρά συνεκτικών συνιστωσών προσέξτε αυτό είναι ένα διαφορετικό πρόβλημα από το αν ένα γράφημα ενισχύοντας συνεκτικό όπως εδώ για παράδειγμα βλέπετε αυτό δεν είναι ένα ισχυρό συνεκτικό υπογραφή του αρχικού γράφημα τους ωραία και θέλουμε να ανακαλύψουμε τέτοιες δομές τι σημαίνει λοιπόν καταρχήν ισχυρά συνέδριο συνιστώσα είναι ένα μέγιστο σύνολο κορυφώνουν έτσι ώστε για κάθε κομμάτι που ανήκει στο σύνολο και ανήκε στο γράφημα υπάρχει διαδρομή και από το ίδιο συνέβη και αποτελεί στοιχείο φορά και ουσιαστικά αυτό το σύνολο έχει κεφάλαιο ορίζει ένα παγωμένο υπογράφει μιλάμε προφανώς μονοσήμαντο τρόπο το οποίο είναι ισχυρό συνεκτικό πείτε λοιπόν έχετε αυτό το δεδομένο γράφημα και εδώ βλέπω τις ισχυρά συνεκτικές συνιστώσας δηλαδή αυτές οι ρήτρες κορυφαίες ανήκουν σε ένα ισχυρή συνεκτική συνιστώσα που σημαίνει αν εγώ προσπαθήσω νέα εποχή κάποιοι αυτό το μέγιστο δυνατό υποσύνολο που περιλαμβάνει αυτές τις κορυφές γιατί αν προσπάθησε για παράδειγμα να βάλω μέσα την κορυφή C την κορυφή κατηγορηθεί ευχή για παράδειγμα ωραία μπορείτε να δείτε ότι υπάρχει διαδρομή από την Λιβύη προς την ΕΥΠ αλλά από την αθήνα δεν υπάρχει καμία διαδρομή προς τις πως κάποια από τις ήδη η κεντρική ωραία θα πρέπει δηλαδή υδατογράφημα αυτό που προκύπτει το παγωμένο υπογραφή από το συλλογικό εφαλτήριο θα πρέπει να είναι ισχυρά συνεκτικό υπογράφει ότι υπάρχει ένα παράγων αυτό έχει πολλές σημαντικές εφαρμογές σε πολύ μεγάλα γραφήματα γιατί θέλουμε να βρούμε ουσιαστικές συνιστώσες για να δούμε για παράδειγμα τις σχέσεις μεταξύ διαφόρων οντοτήτων να ανακαλύψουμε κλίκες φιλίες μεταξύ ανθρώπων κλπ τώρα για να δούμε ένα μια ίσια να δούμε τις ισχυρά συνεκτική συνιστώσα ένα κατευθυνόμενο γραφημάτων ως θα χρειαστούμε το λεγόμενο αναστροφή γράφημα ένα κατευθυνόμενα γραφήματα το οποίο προκύπτει αυτό το πανάκριβο γράφημα απλά αν αντιστρέψουμε τη φόρα των ατόμων του αρχικού αλλά αυτό είναι το DJ και αυτόν τον τζέι αναστραφούν και παρατηρείται ότι ακόμα και μετά την αναστροφή των άγαμων έχουν ακριβώς της Σητείας συνεκτικές συνιστώσας δηλαδή το υπογράφει μα αυτό εφόσον υπάρχει διαδρομή μεταξύ των τριών κορυφαίων οποιαδήποτε κορυφή αποτίσει ήδη προσωπεία τίποτα από χτες βλέπε ότι ανήκουν σε ένα κύκλο αυτές τις κορυφαίες δωρεά δεν έχει σημασία αν διατρέξει τον κύκλο αυτό δεξιόστροφα και αριστερόστροφα το σημαντικό είναι γιατί αυτό σημαίνει αλλαγή φοράς ακουμπούν το σημαντικό είναι ότι αυτές ενώ οι τρεις κορυφαίες ανήκουν στην ίδια σύγχυση γράψτε τη συνιστώσα γιατί επαναλαμβάνω οι κορυφές είναι που προσδιορίζουν με μοναδικό τρόπο την ουσιαστική συνιστώσα αφού το υπογράφουμε που δημιουργείται είναι παγωμένο υπογράφοντας θα πρέπει να πάνε στην κα όλες τις ακμές μεταξύ των κολλητών κορυφών αυτών χόρευε υπάρχει λέγεται αναστροφή για τυχαίο τρόπο γιατί αν για παράδειγμα υποθέσετε την αναπαράσταση σε μητρώα σε μητρώο και μειώσεις τότε έχετε τον Πόνζι να παρασιτούν ζει με του αναστροφή που είναι ακόμα κοντά στο μητρώο του αρχικού Μήτρου του και τώρα πια είναι ιδέα του αλγόριθμου για να βρούμε τις ισχυρά σημαντικές συνιστώσες είναι η εξής ότι εάν ξέραμε πείτε ότι κάποιος σας δίνει τις αρχές και τις ισχυρά συνεκτικές μίσθωσης και αυτό που κάνετε είναι συρρικνώνεται της ισχυρά συνεπή υπεύθυνης τόσος σε ένα κορυφή φορέα δηλαδή το την κόκκινη κίτρινη πράσινη και μπλε προκύπτει ένα γράφημα το ίδιο συμβαίνει και απότομη στροφή είναι ακριβώς το ίδιο ωραία προκύπτει ένα γράφημα παρατηρήστε έτσι σημαντική παρατήρηση είναι ότι το γράφημα το οποίο προκύπτει είναι ένα κατευθυνόμενο κυκλικό γράφει και ουσιαστικά ο αλγόριθμος των οποίων θα σας περιγράψω σε λίγο είναι σαν να επισκέπτεται τις ακμές αυτού του πόλου του κατευθυνόμενο κυκλικού σχήματος κατά τόπο λογική διάταξη την οποία δεν γνωρίζει ωραία και το κάνει αυτό εργάζομαι εργαζόμενος όμως αλγόριθμος στου αναστροφή γράφημα ουσιαστικά ανακαλύπτει αυτές τις κορυφές και κάτι μου cover κατά συνέπεια και της ισχυρά συνεκτικές συνιστώσες δουλεύω δουλεύοντας ως εγώ αλλά στο γράφημα πάμε να δούμε πώς συμβαίνει αυτό αυτό που κάνουμε είναι αυτή τι επαναλαμβάνει μια εφαρμογή της αναζήτησης πρώτα καταβάθος ξεκινάμε πάλι με χρόνους καταληψίες βρίσκουμε την σύγχρονους εγκατάλειψης στο αρχικό γράφημα μετά δημιουργούμε το αναστροφή γράφημα και τι κάνουμε εκτελούμε τώρα αναζητήσει πρώτα κατά βάθος στο πάνω στο γράφημα αλλά στον κύριο λόγο παίρνουμε τις κορυφές σε δεν θέλουμε τις κορυφές με αυθαίρετο τρόπο τις παίρνουμε σε φθίνουσα σειρά ως προσπάθεια του ίδιου εάν θυμάστε Γι' αυτό σας είπα και πριν τον αλγόριθμο τον άλλο εναλλακτικό της τοπολογία διατάξεις ότι η φθίνουσα κατά σειρά των κόμβων καταρχήν να εγκαταλείψεις καταχρώνται καταλήψεις δίνει ένα απολογητική διατάξεις ένα κατευθυνόμενο κυκλικό γράφει αυτό λοιπόν εκμεταλλευόμαστε εδώ και λέμε ότι στον κύριο βρόχου λοιπόν παίρνουμε τις κορυφές ευθύνης διάταξη ως προς το χρόνο οι καταλήψεις και αυτό με κάποιο τρόπο που τώρα θα δούμε αμέσως απομονώνει τις ισχυρά θετικές συνιστώσες σαν αυτούς τους υπερ κόμβους που δημιουργήσαμε εδώ δημιουργεί δηλαδή ανακαλύπτει αυτούς πάρκο μουσικού αντιστοιχούν σε αυτές τις κρίσιμες συνθήκες συνιστώσες σαν δέντρα του δάσους που δημιουργούνται από την αναζήτηση πρώτα καταβάθος ωραία πάμε να δούμε ενα παράδειγμα κοιτάξτε ξεκινάμε να κάνουμε αναζήτηση κατά βάθος από την κορυφή C εδώ πριν την πάμε αποτίμηση τώρα με ένα δίνουμε χρόνο ένα τάματα στην κορυφή GE δίνουμε χρόνο δύο στη ανακαλύπτουμε την κορυφή αυτή χρονική στιγμή τρεις μετά από την ευθεία έχει μόνο ένα εξερχόμενη ακμή η οποία μας οδήγησε ένα με την οποία έχουμε ήδη ανακαλύψει ωραία τότε θα εγκαταλείψουμε την κορυφή και θα δώσουμε νοούμενο 4χρονο καταλήψεις τέσσερις και επιστρέφουμε στην κορυφή έτσι από την κορυφή έτσι πηγαίνουμε στην κορυφή της αυτήν την εξερχόμενη δεν την έχουμε δει ούτε την κορυφή έτσι πούνε ανακαλύπτουμε τη χρονική στιγμή πέντε μετά από την είδηση δεν έχουμε ακόμα μια ακόμη εγκαταλείπουμε την κορυφή έτσι τη χρονική στιγμή έξι και επιστρέφουμε στην αναδρομική κλήση στην κορυφή έτσι AG δεν έχει άλλη εξερχόμενη ακόμη και επομένως επιστρέφονται νομική έκλεισε στην κορυφή αίρεση που τώρα έχει και ένα άλλη εξερχόμενη ακμή της CD που δεν έχουμε δει ανακαλύπτουμε την κορυφή Δείτε χρόνια 1008 εγκαταλείπουμε τη χρονική στιγμή 9 γιατί γιατί ήδη έχει ένα εξερχόμενη που μας οδηγεί στην κορυφή έτσι την οποία όμως έχουμε ήδη δει και επιστρέφουμε στην κορυφή συ τώρα από την κορυφή εσείς δεν έχουμε πουθενά να πάμε δεν υπάρχουν έχουμε εξαντλήσει εξερχόμενος μέσα και επιλέγουμε τυχαία καμιά από τις υπόλοιπες τρεις κορυφές που μας που δεν έχουμε δει και πείτε ότι διαλέγουμε την κορυφή BMI την οποία ανακαλύπτουμε τη χρονική στιγμή 11 αυτή έχει 1.2 έξι ακόμα στην αυτή την έχουμε δει αντιστραφεί πίσω βλέπουμε ότι ανακαλύπτουμε την ήδη μέσω της ακμής συμβεί η χρονική στιγμή 12 αυτή έχει δύο εξαρτώμενες ήδη αφού μας οδηγεί στην οποία έχουμε δει μ ν μας οδήγησαν νέα κορίτσια που δεν έχουμε δει και ανακαλύπτουμε τη χρονική στιγμή 13 και ενώ είμαστε στην κορυφή έχει λέει έχει εξαρτώμενη την ιδέα την οποία όμως έχουμε ήδη επισκεφθεί επομένως καταλήγουμε την ίδια χρονική στιγμή 14 επιστρέφουμε στη ν την οποία καταλήγουμε να έχουμε έτσι τα επόμενα χρόνια στην 15 και επιστρέφουμε στην κορυφή b που δεν έχει άλλη έχει καλύψει ακόμη ένα ακόμη πρόκληση στην οποία έχουμε δει και την εγκαταλείπουμε τη χρονική στιγμή 16 επομένως αυτή εδώ η αρίθμηση με χρόνους ανακάλυψαν στρατηγών εγκατάλειψης δεξιά είναι ένα αναζήτηση πρώτα καταβάθος ξεκινώντας στο γράφημα αυτό από την κορυφή C τώρα τι λέει αλγόριθμος λέει ότι δημιούργησε το αναστροφή γράφημα και εκτέλεσε την αναζήτηση καταβάθος παίρνοντας τις κορυφαίες σε φθίνουσα σειρά ως προς το χρόνο οι καταλήψεις γονέα ποια είναι δηλαδή λέει δημιούργησε αυτό το γράφημα υπογρα και ξεκινά την αναζήτηση πρώτα κατά βάθος στο γράφημα αυτό ξεκινώντας από την κορυφή πιο είναι κορυφή που έχει τον μεγαλύτερο χρόνο ανακαλύψεις πολύ σωστά κορυφαίοι μπαίνει χώρα κορυφή αντί λοιπόν να εργαζόμαστε εδώ θα βρω την κορυφή εισάγονται κορυφή γι ωραία δε μας ενδιαφέρουν δύο χρόνια ανακαλύψτε κατάληψη αυτούς έχουν σημειώσει αυτό που έχει σημασία είναι ότι θα φτάσω στην κορυφή και έχω να πάω έχω διέρρευσαν δύο ένα εξερχόμενη την ινδή βουνού επιστρέφει σε ένα κορυφή την οποία έχω δει και βλέπετε ότι δεν μπορώ να ανακαλύψω άλλες κορυφές εργαζόμενους στου αναστροφή γράφημα επομένως αυτή το θέατρο δηλαδή γνωρίζαμε τι θα δείτε το trailer και εγγόνια του την κορυφαίοι οίκοι είναι ένα ισχυρά συνεκτική συνιστώσα που αποτελείται από τις κορυφές b εκείνη αναστροφή δηλαδή εγκλωβίζεται να αναζητήσει πρώτα κατά βάθος εντός της ισχυρά συνεκτική συνιστώσα και δεν με αφήνει να βγω έξω από την κόκκινη συνήθως δεν υπάρχει εξερχόμενη έχουμε και θα το αποδείξουμε αυτό ότι δεν υπάρχεις έχουνε με το δίκαννο αφού τελείωσα με αυτές δηλαδή έχω δε την αντικειμενική τιμή ποια είναι η αποχή από τις υπόλοιπες πέντε κορυφαίες ποια είναι εκείνη με την τον μεγαλύτερο χρόνο καταλήψεις κλπ οι κορυφαίοι σε ωραία πάω λοιπόν εδώ και έχω ένα εξερχόμενη προς την με την οποία έχω δει αλλά δεν έκαναν τίποτα ανακάλυψα τίποτα καινούργιο και ένα προς την η οποία δεν έχω δει στον στόχο γράφημα και την οποία ανακαλύπτουν από την κορυφή διοι δέν έχω έχω μόνο ένα εξερχόμενη πρόσθεσε η οποία την οποία έχω ήδη δει και καμία άλλη εξερχόμενη σταματάει λοιπόν εδώ η αναζήτηση πρώτα καταβάθος και μου δίνει εναν θέατρο γνωρίζατε βοηθήσει και απέδιδε την κορυφή αντί αυτής δηλαδή οι δύο κορυφαίες μου καθορίζουν τη δεύτερη ισχυρά συνεκτική συνιστώσα μετά από τις υπόλοιπες τρεις κορυφαίες αυτή που έχει ήδη γίνει τον μέγιστο χρόνο εγκατάλειψης είναι η κορυφή έτσι η κορυφή έτσι λοιπόν ξεκινούν την αναζήτηση πρώτα καταβάθος έχει ένα εξερχόμενη πρόσκληση την οποία έχω δει επομένως δεν έχω νέα πληροφορία και ένα εξερχόμενη προς την κορυφή γράφει οινοποιίας στον άξονα στο γράφημα την πρώτη φορά που βλέπουμε boots πηγαίνω στην κορυφή αυτό από δω έχω τώρα εξερχόμενες προς την ΔΕΗ και μπροστινή και προσθέτει ζει τρεις δηλαδή όλες από τις οποίες έχω ήδη δει επομένως η αναζήτηση πρώτα κατά βάθος επιστρέφει στην κορυφή έτσι ρε η οποία έχει μόνο μια λέξη έχομε υπόσχεση που έχω δει και τελειώνει ολοκληρώνεται η αναζήτηση καταβάθος αναστροφή γράφημα ξεκινώντας από την κορυφή ζει ανακαλώντας μόνο θέσεις δύο κορυφές λεχώνα δέντρο νεράντζι και φαίνεται ότι είναι μόνο δύο κόσμους και τέλος πάνω στην κορυφή AIDS επομένως έχω τέσσερις ισχυρά σημαντικές συνιστώσες όπως ήδη γνωρίζουμε και μπορούμε να υπολογίσουμε με τομάτα χώρα χρόνος πώς το λένε εκτέλεσης του αλγορίθμου είναι απλές εφαρμογές του αλγόριθμου στο πρώτο επεισόδιο το βήμα του αλγόριθμου αναζήτησης των καταβάθος που παίρνει γραμμικό χρόνο στο πλήθος των κορυφών και τον κόσμο έχουμε δει σε προηγούμενο μάθημα σε προηγούμενη διάλεξη και το μόνο που μένει είναι η δημιουργία από το αρχικό του αναστροφή γράφημα κι αυτό μπορεί να πάρει πιστέψτε με γραμμικό χρόνο και σας αφήνω σαν άσκηση αν δεν σας είναι προφανές είναι πάρα πολύ εύκολο αν σας δίνεται ένα γράφημα να φτιάξετε τον στόχο του όπως είναι πάρα πολύ εύκολο όταν έχετε ένα μητρώο να βρει τον στόχο αυτό που έχει σημασία είναι η ορθότητά του αλγόριθμου και με αυτό θα κλείσουμε τη σημερινή διάταξη και η ορθότητα προκύπτει ως εξής καταρχήν συμβολίζουν δικέφαλο έναντι του κεφάλαιο και το ελάχιστο τη Γιουνγκ ανήκει σε ένα υποσύνολο κορυφών δηλαδή έχω ένα υποσύνολο 10 δορυφόρων κοίτα αυτές τις 10 Κόροιβος ελέω PSI είναι η κορυφή με τον μικρότερο χρόνο ανακαλύψεις αυτή είναι τον λειτουργεί κεφάλαιο και αντίστοιχα πιάνει κορυφή με το μεγαλύτερο χρόνο εγκατάλειψης αυτό προσδιορίζει το FPO δικέφαλο φορέα και αυτό που επαναλαμβάνω προκύπτει από την ορθότητα αποδεικνύουν την ορθότητα τούλι του προηγούμενου αλγορίθμου νότια εγώ κοιτάξω δύο διαφορετικές αν συντάκτη ισχυρά συνεκτικές συνιστώσες στο αναστροφή γράφημα στο σίτι και σηκώνουμε κεφάλι λέω ωραία και κοιτάξω ένα ακμή που βγαίνει από το v που ένα κόμμωση των ηνωμένων στο you τότε ο χρόνος κατάληψη στους φ συνιστώσα σε που δεν ξέρω είναι μεγαλύτερος από το χρόνο οι καταλήψεις της συνιστώσας σηκώνουν μόνο αυτό σημαίνει ουσιαστικά ότι εγώ δεν μπορώ να βρω δηλαδή πλευρά που να ΟΤΑ που όταν τρέξω ένα αναζήτηση πρώτα καταβάθος στην συνιστώσα C να με οδηγεί σε κάποια κορυφή του σηκώνουν ενώ φορέα προσέξτε αν εγώ αυτή είναι η κατάσταση στο αρχικό μου γράφημα όπου UV έχει την αντίθετη κατεύθυνση και για να αποδείξω αυτό το έλλειμμα που σας είπα επαναλαμβάνω εδώ γιατί δεν μπορούσα να βγω έξω από την Κομοτηνή συνιστώσα γιατί όλες αυτές οι ακμές από την κίτρινη και πράσινη μπλε βλέπετε ότι πηγαίνουν από προς την κόκκινη συνιστώσα και δεν εξαιρούνται της προτίμησής σας αυτό ουσιαστικά λέει αυτό εδώ το βήμα απόδειξη την απλή δηλαδή θα αποδείξουμε για το κανονικό γράφημα όταν η ακμή πάει από το γιο στον δη θέλουμε δηλαδή να αποδείξουν να αποδείξουμε ότι έστω ότι έχουμε δύο διαφορετικές ισχυρά συνεκτικές συνιστώσες στο αρχικό μου γράφημα συνοικέσιο των ηνωμένων που συνδέονται με ένα ν UV και θέλουμε να αποδείξουμε ότι χρόνος εγκατάλειψης της συνιστώσας Σύροι του υποσύνολο των κορυφών C είναι μεγαλύτερος από εκείνη του υποσύνολο των κορυφών σηκώνουμε νέα αυτό υπάρχουν δύο περιπτώσεις άνω χρόνος 9 ανακαλύψεις της συνιστώσας είναι μικρότερος από εκείνον της των Ηνωμένων η το αντίστροφο ας πάρουμε την πρώτη περίπτωση πορεία τι συμβαίνει εδώ εύστοχη η πρώτη κορυφαίοι την οποία ο αλγόριθμος αναζήτησης καταβάθος το κόστος ανακαλύπτει δηλαδή των αντί του όχι είναι το δικό τους κεφάλαιο αυτό σημαίνει ότι όλες οι κορυφαίες με W.E. στο σύντομο μέλλον είναι προσπελάσιμοι μέσω της χ από προσπελάσιμοι όλες τις κορυφαίες 20 και μέσω της τέχνης UV θα προσπέλαση έξι όλες τις κορυφές έκδοση των λουομένων αφού το ζητούμενο είναι μια ισχυρή συνεκτική συνιστώσα που σημαίνει ότι αφού τα δω όλες τις κορυφές της των ηνωμένων φορέα και τις ανακαλύψω μέσω της πλευράς UV και μέσω του διαφαίνεται θα εγκαταλείψω όλες αυτές τις κορυφές των ζητούμενων και μετά θα επιστρέψω στην κορυφή u που προκάλεσε την αναδρομική κλήση του αλγόριθμου αναζήτησης πρώτα καταβάθος και θα εξερευνήσουν τις υπόλοιπες κορυφές του C και μετά θα καταλήξω τόση αυτό σημαίνει δηλαδή οδύνη τη κορυφή έχει την οποία ξεκίνησα εγώ την αναζήτηση πρώτα καταβάθος τόση θα είναι η τελευταία που θα έχει η τελευταία που θα εγκαταλειφθεί από τη συνιστώσα συλλη φορέα και θα δώσει τιμή στο αυτούς κεφάλαιο και επιπλέον θα είναι μεγαλύτεροι από αυτούς το νουμερο δηλαδή από το χρόνο καταλήψεις οποιασδήποτε κορυφής στην ισχυρά συνεκτική συνιστώσα στο ηνωμένο καταλαβαίνουμε γιατί πρέπει πρώτα να εγκαταλείψω όλες αυτές και να επανέλθουν στο C Επομένως στην περίπτωση αυτή το απέδειξε πάμε να δούμε στην άλλη περίπτωση όταν τον τους συ δηλαδή η ανακάλυψή τους σηκώνουν ενώ προηγείται της ανακάλυψης τους η μα στην περίπτωση αυτή όλα εγώ ξεκινάω από κάποια κορυφή Ψηλή η οποία δίνει ο χρόνος ανακαλύψεις της δίνει τον χρόνο ανακαλύψεις συντονισμένων και αφού πρώτη κορυφή αυτήν ισχυρά συνεκτική συνιστώσα θα τις ανακαλύψω όλες οι κορυφές του ζητούμενου αλλά επειδή δεν υπάρχει ακόμη που να οδηγεί αποχωρεί φοιτούσε των ηνωμένων σε εκείνη του σε να εγκαταλείψουν κρίση κορυφές στο συντονισμένων πριν ξεκίνησε την ανακάλυψη των κορυφών του σι επομένως που θα εγκαταλείψουν τις κορυφές εδώ στο σύντομο μέλλον σίγουρα θα τις εγκαταλείψουν όλες πριν κανά ανακάλυψε και άρα και καταλήψεων οποιαδήποτε κορυφής όσοι επομένως και σ'αυτή την περίπτωση ισχύει το κλίμα αυτό και όπως σας είπα ήδη χρονική πολυπλοκότητα του αλγορίθμου είναι γραμμική για το λόγο που συζήτησα πρωί έτσι επαναλαμβάνω όλο το ζήτημα εδώ είναι η απόδειξη ότι τας που βασίζεται σε αυτό το κλίμα και το οποίο μπορείτε και με ησυχία να δείτε εκεί αν δεν το καταλάβατε επέτειο χρόνος τελειώνει θα το συζητήσουμε στο επόμενο μάθημα καλό μεσημέρι παιδιά |
