Ανάλυση μέσης περίπτωσης αλγορίθμων ψαξίματος σε γράφους

Abstract

We estimate the expected value of various search quantities for a variety of graph-searching methods, for example \dfs\ and \bfs. Our analysis applies to both directed and undirected random graphs, and it covers the range of interesting graph densities, including densities at which a random graph is disconnected with a giant connected component. We estimate the number of edges examined during the search, since this number is proportional to the running time of the algorithm. We find that for hardly connected graphs, all of the edges might be examined, but for denser graphs many fewer edges are generally required. We prove that any searching algorithm examines {$\Theta(n \log n)$} edges, if present, on all random graphs with {$n$} nodes but not necessarily on the complete graphs. One property of some searching algorithms is the maximum depth of the search. In \dfs, this depth can be used to estimate the space needed for the recursion stack. For random graphs of any density, even for disconnected graphs, we prove that this space is {$\Theta(n)$}. On the other hand, the depth of \bfs\ is {$\Theta(\log n / \!\log(p n))$}, where {$p$} is the probability of the existence of an edge. The size of the \dstr\ needed by any searching algorithm is proved to be {$\Theta(n)$}. If the search terminates at a particular node, any searching algorithm needs a \dstr\ of size {$\Theta(n)$}, and examines only {$\Theta(n)$} edges. Finally, we derive similar results for variants of the above searching algorithms, more general classes of searching algorithms, and for random graphs with multiple edges. These results are verified through simulations. The techniques employed to permit simulations of big graphs (few millions of nodes) and the results obtained are of general interest, especially to those performing similar experiments.

Υπολογίζουμε την προσδοκόμενη τιμή διαφόρων ποσοτήτων για μια ποικιλία από μεθόδους ψαξίματος σε γράφους, όπως στο depth-first search και στο breadth-first search. Η ανάλυσή μας εφαρμόζεται σε κατευθυνόμενους και μη κατευθυνόμενους τυχαίους γράφους και καλύπτει την περιοχή των ενδιαφέρουσων πυκνοτήτων των γράφων, περιλαμβάνοντας πυκνότητες στις οποίες ο τυχαίος γράφος αποτελείται από περισσότερες από μία συνιστώσες και έχει μία γιγαντιαία συνιστώσα. Υπολογίζουμε τον αριθμό ακμών που εξετάζεται κατά τη διάρκεια του ψαξίματος, καθώς αυτός ο αριθμός είναι ανάλογος με το χρόνο τρεξίματος του αλγορίθμου. Βρίσκουμε πως για γράφους που μόλις είναι ενωμένοι, μπορεί να εξετάσουμε όλες τις ακμές, αλλά για πυκνότερους γράφους γενικά χρειάζονται πολύ λιγότερες ακμές. Αποδεικνύουμε πως οποιοσδήποτε αλγόριθμος ψαξίματος εξετάζει Θ(n logn) ακμές, εφόσον υπάρχουν, σε όλους τους τυχαίους γράφους με n κόμβους, αλλά όχι απαραίτητα και στους πλήρεις γράφους. Μία ιδιότητα μερικών αλγορίθμων ψαξίματος είναι το μέγιστο βάθος του ψαξίματος. Στο depth-first search, αυτό το βάθος μπορεί να χρησιμοποιηθεί για να προσδιορίσουμε το χώρο που απαιτείται για τη στίβα της αναδρομής. Για τυχαίους γράφους οποιασδήποτε πυκνότητας, ακόμα και για μη συνδεμένους γράφους, αποδεικνύουμε ότι αυτός ο χώρος είναι Θ(n). Από την άλλη μεριά, το βάθος που φτάνει το breadth-first search είναι Θ(logn/log(pn)), όπου p είναι η πιθανότητα ύπαρξης οποιασδήποτε ακμής. Αποδεικνύουμε ότι το μέγεθος της δομής δεδομένων που απαιτείται από oποιονδήποτε αλγόριθμο ψαξίματος είναι Θ(n). Αν το ψάξιμο τελειώνει μόλις φτάσουμε ένα συγκεκριμένο κόμβο, αποδεικνύουμε ότι oποιοσδήποτε αλγόριθμος ψαξίματος χρειάζεται μια δομή δεδομένων μεγέθους Θ(n), και εξετάζει μόνο Θ(n) ακμές. Τελικά, παράγουμε παρόμοια αποτελέσματα για παραλαγές των παραπάνω αλγορίθμων ψαξίματος, περισσότερο γενικές τάξεις αλγορίθμων ψαξίματος, και για τυχαίους γράφους με πολλαπλές ακμές. Αυτά τα αποτελέσματα επιβεβαιώνονται με εξομοιώσεις. Οι τεχνικές που χρησιμοποιήθηκαν για να κάνουν δυνατή την εξομοίωση μεγάλων γράφων (με μερικά εκατομμύρια κόμβους) και τα αποτελέσματα που βγήκαν είναι γενικού ενδιαφέροντος, ειδικά για αυτούς που εκτελούν παρόμοια πειράματα.