Γράφοι

Ορισμοί

• Ένας γράφος (graph) είναι ένα σύνολο από κόμβους που ενώνονται με ακμές.
• Ο γράφος ορίζεται πλήρως από τους κόμβους και τη συνδεσμολογία τους.
• Αν οι ακμές είναι προσανατολισμένες (ορίζονται δηλαδή από διατεταγμένα ζεύγη κόμβων) τότε ο γράφος λέγεται κατευθυνόμενος (directed).
• Αν οι ακμές δεν είναι προσανατολισμένες (ορίζονται δηλαδή από μη διατεταγμένα ζεύγη κόμβων) τότε ο γράφος λέγεται μη κατευθυνόμενος (undirected).
• Αν οι ακμές είναι συνδεδεμένς με κάποια αξία (βάρος) τότε ο γράφος λέγεται σταθμισμένος (weighted).
• Πλήρης (Complete) ορίζεται ο μη κατευθυνόμενος γράφος που περιέχει ακμές που ενώνουν κάθε ζεύγος κόμβων.
• Αραιός καλείται ο γράφος που περιέχει λίγες σχετικά ακμές (λ.χ. για ν κόμβους ο αριθμός των ακμών < ν log ν).
• Πυκνός (Dense) καλείται ο γράφος από τον οποίο απουσιάζουν λίγες σχετικά ακμές.

Παράσταση

1. πίνακα γειτνίασης (adjacency matrix).
2. λίστα γειτνίασης (adjacency list).

Πίνακας γειτνίασης

Λίστα γειτνίασης

Υλοποίηση σε Pascal

Πίνακας γειτνίασης

program matrixGraph;

const
    n = 10;	(* Number of nodes *)

var
    graph = array [1..n,1..n] of boolean;

...

Λίστα γειτνίασης

program listGraph;

const
    n = 10;	(* Number of nodes *)

type
    adjList = ^adjListElem;

    adjListElem = record
        node : integer;
        next : adjList;
    end;

var
    graph = array [1..n] of adjList;

...

Πρόσθετοι ορισμοί

• Διαδρομή (path) καλείται μια διάταξη κόμβων οι οποίοι ενώνονται με ακμές.
• Απλή διαδρομή (simple path) καλείται η παραπάνω διάταξη όταν κάθε κόμβος εμφανίζεται μια μόνο φορά.
• Κύκλος (cycle) καλείται η διαδρομή δύο ή περισσοτέρων κόμβων που καταλήγει στον κόμβο αρχής.
• Απόσταση (distance) μεταξύ δύο κόμβων καλείται το μήκος της συντομότερης διαδρομής που τους ενώνει.
• Διαδρομή Euler (Euler path) καλείται η διαδρομή ή οποία περνάει από όλες τις ακμές του γράφου ακριβώς μια φορά.
• Διαδρομή Hamilton (Hamilton path) καλείται η διαδρομή ή οποία περνάει από όλους τους κόμβους του γράφου ακριβώς μια φορά.
• Γράφοι που περιέχουν τις παραπάνω διαδρομές ονομάζονται αντίστοιχα.
• Συνεκτικός (connected) ονομάζεται ο γράφος για τον οποίο υπάρχει διαδρομή από κάθε κόμβο σε κάθε άλλο κόμβο.
• Βαθμός ενός κόμβου σε έναν μη κατευθυνόμενο γράφο καλείται ο αριθμός των συνδεδεμένων με αυτόν ακμών.
• Βαθμός εισόδου (in-degree) σε έναν κατευθυνόμενο γράφο καλείται ο αριθμός των ακμών που καταλήγουν σε αυτόν.
• Βαθμός εξόδου (out-degree) σε έναν κατευθυνόμενο γράφο καλείται ο αριθμός των ακμών που ξεκινούν από αυτόν.
• Υπογράφος (subgraph) Β ενός γράφου Α καλείται ο γράφος του οποίου όλες οι ακμές και οι κόμβοι περιέχονται στον Α.
• Δένδρο σκελετός (spanning tree) ενός γράφου καλείται ο υπογράφος που περιέχει όλους του κόμβους αλλά μόνο όσες ακμές απαιτούνται για να σχηματιστεί δένδρο.

Προτάσεις σε συνεκτικούς μη κυκλικούς γράφους

1. Ο γράφος Γ είναι συνεκτικός και μη κυκλικός.
2. Αν διαγραφεί οποιαδήποτε ακμή ο γράφος θα πάψει να είναι συνεκτικός.
3. Δύο διαφορετικοί κόμβοι συνδέονται από μια και μόνο μια απλή διαδρομή.
4. Ο γράφος είναι μη κυκλικός και περιέχει ν - 1 ακμές.
5. Ο γράφος είναι συνεκτικός και περιέχει ν - 1 ακμές.

Ψάξιμο κατά βάθος

1. Φυλάμε την τιμή "ψευδές" στον πίνακα επισκέψεων.
2. Επισκεπτόμαστε όλους τους κόμβους που δεν έχουμε επισκευτεί.

1. Σημειώνουμε στον πίνακα ότι έχουμε επισκευθεί τον κόμβο.
2. Επισκεπτόμαστε όλους τους συνδεδεμένους κόμβους που δεν έχουμε επισκευθεί.

• Για γράφο που παριστάνουμε με πίνακα γειτνίασης χρόνο ανάλογο με Κ * Κ.
• Για γράφο που παριστάνουμε με λίστα γειτνίασης χρόνο ανάλογο με Κ + Α.

Εφαρμογές

• Παράσταση διασυνδέσεων ανάμεσα σε αντικείμενα
  • Ταξίδια ανάμεσα σε πόλεις
  • Συνδέσεις υπολογιστών σε δίκτυο
  • Συνδέσεις σελίδων σε υπερκείμενο
  • Ανθρώπινες σχέσεις
• Παράσταση ηλεκτρονικών διαγραμμάτων
• Προγραμματισμός εργασιών

Βιβλιογραφία

• Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 98-105 Εκδόσεις Νέων Τεχνολογιών, 1993.

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms, pages 172–309. Addison-Wesley, 1974.
• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms, pages 198–252. Addison-Wesley, 1983.
• Donald E. Knuth. The Art of Computer Programming, volume 1 / Fundamental Algorithms, pages 362–378. Addison-Wesley, second edition, 1973.
• Robert Sedgewick. Algorithms in C, pages 415–508. Addison-Wesley, 1990.

Ασκήσεις

Άσκηση ADS06

1. Να υλοποιηθεί σε Pascal πρόγραμμα το οποίο διαβάζει ζεύγη συνδεδεμένων κόμβων ενός γράφου ακεραίων μέχρι να συναντήσει το ζεύγος (0,0) και στη συνέχεια επισκέπτεται κατά βάθος όλους τους κόμβους και τυπώνει τον αριθμό τους στο τέλος της διαδικασίας επίσκεψης.

   Παράδειγμα:

   5 3
   5 2
   0 2
   4 0
   0 5
   1 6
   1 5
   0 0
   
   
   2
   3
   5
   0
   6
   1
   

   Αριθμήστε στην τύχη όλα τα ρούχα σας (π.χ. παπούτσια = 1, κάλτσες = 6) και εκφράστε την έννοια ότι για να φορέσετε το Α πρέπει να έχετε φορέσει το Β ως ένα ζεύγος (Α, Β) (π.χ. 1 6). Δώστε όλα τα ζεύγη που εκφράζουν τις ανάγκες σας για να ντυθείτε με λογικό τρόπο και ελέγξτε την σειρά ενδυμασίας που προτείνει το πρόγραμμα. (Η ταξινόμιση αυτή ονομάζεται τοπολογική ταξινόμιση (topological sorting)).

• Περιεχόμενα

 Τελευταία αλλαγή: Τρίτη, 19 Σεπτεμβρίου 2006 6:30 μμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».