Γράφημα

Συζητήσεις για την γλώσσα C και C++

Συντονιστές: Super-Moderators, WebDev Moderators

Απάντηση
ethnikos
Δημοσιεύσεις: 39
Εγγραφή: 03 Μαρ 2006 15:13

Γράφημα

Δημοσίευση από ethnikos » 03 Μαρ 2006 16:59

askisi se c

Κώδικας: Επιλογή όλων

http://rapidshare.de/files/14586710/___________4.doc.html

ethnikos
Δημοσιεύσεις: 39
Εγγραφή: 03 Μαρ 2006 15:13

Γράφημα

Δημοσίευση από ethnikos » 04 Μαρ 2006 10:52

AFTI EINAI I ASKISI XORIS TIS 2 EIKONES....GIA NA TIN DEITE OLI KATEVASTE TO ARXEIO DOC
----------------------------------
Ένα από τα πιο θεμελιώδη μαθηματικά αντικείμενα, με πλήθος εφαρμογών στην Επιστήμη των Υπολογιστών, είναι το Γράφημα. ¨Ένα γράφημα αποτελείται από έναν αριθμό αντικειμένων, τις κορυφές, και έναν αριθμό συνδέσεων μεταξύ ζευγών των αντικειμένων αυτών, τις ακμές. Ένα παράδειγμα γραφήματος είναι το ακόλουθο:

Το γράφημα αυτό θα μπορούσε να αναπαριστά, για παράδειγμα, 5 πόλεις και τους εθνικούς δρόμους που τις συνδέουν, εάν υπάρχουν (η πόλη 2, που δεν φαίνεται να συνδέεται με τις άλλες, μπορεί να βρίσκεται, π.χ. σε κάποιο νησί).
Ένα γράφημα έχει μία πολύ κομψή και εύχρηστη αναπαράσταση με ένα διδιάστατο (2D) πίνακα, που ονομάζεται πίνακας γειτνίασης, στον οποίο η θέση (i,j) περιέχει 0 εάν δεν υπάρχει σύνδεση μεταξύ των κορυφών i και j ενώ εάν υπάρχει σύνδεση, η θέση (i,j) περιέχει 1. Στο παράδειγμα μας, το γράφημα μπορεί να αναπαρασταθεί με έναν 5 Χ 5 πίνακα ως εξής:

Κοιτώντας, για παράδειγμα, την πρώτη γραμμή βλέπουμε ότι η κορυφή 1 συνδέεται με τις κορυφές 4 και 5. Λέμε τότε, ότι ο βαθμός (degree) της είναι ίσος με 2, καθώς συνδέεται με 2 κορυφές. Κοιτώντας τη δεύτερη γραμμή, βλέπουμε ότι η κορυφή 2 δεν συνδέεται με καμία από τις υπόλοιπες κορυφές, πρόκειται δηλαδή για απομονωμένη κορυφή (κορυφή βαθμού 0). Παρατηρήστε ότι ο πίνακας είναι συμμετρικός, δηλαδή εάν υπάρχει 1 (0) στη θέση (i,j) τότε υπάρχει 1 (0) και στη θέση (j,i) (οι συνδέσεις, δηλαδή, είναι αμφίδρομες).
ΣΚΟΠΟΣ
Α) Σχεδιάστε και υλοποιήστε πρόγραμμα σε γλώσσα προγραμματισμού C με τις εξής προδιαγραφές:
1. Να ορίζει ένα διδιάστατο(2D) πίνακα γειτνίασης με NODES στήλες και NODES γραμμές, στον οποίο θα αναπαριστά ένα γράφημα NODES κορυφών (το NODES θα ορίζεται στην αρχή ως σταθερά). Στο παράδειγμα μας πιο πάνω, θα είχαμε πίνακα NODES X NODES= 5 Χ 5.
2. Να ορίζει ένα μονοδιάστατο(1D) πίνακας διάστασης NODES που θα καλείται degrees(βαθμοί). Πάλι στο παράδειγμα μας, ο πίνακας αυτός θα είχε διάσταση NODES=5.
3. Να περιέχει μία συνάρτηση που θα διαβάζει, ένα-ένα, από το πληκτρολόγιο τα στοιχεία του πίνακα γειτνίασης (0 και 1). Θα περιέχει, επίσης, μία συνάρτηση που θα τυπώνει τον πίνακα γειτνίασης στην οθόνη, γραμμή-γραμμή. Στο παράδειγμα μας, θα πρέπει να τυπωθούν NODES=5 γραμμές, κάθε μία από τις οποίες θα περιέχει 5 σύμβολα, 0 ή 1 (χωρισμένα με κενό ή τον χαρακτήρα «,» για παράδειγμα).
4. Να περιέχει μία συνάρτηση που θα υπολογίζει και θα τυπώνει στην οθόνη τους βαθμούς των NODES κορυφών, αποθηκεύοντας τους ταυτόχρονα στον πίνακα degrees. Θα περιέχει, επίσης, δύο άλλες συναρτήσεις που θα επιστρέφουν τους αριθμούς των κορυφών (μπορεί αυτές οι κορυφές να συμπίπτουν σε κάποιους τύπους γραφημάτων!) με το μέγιστο και ελάχιστο βαθμό αντίστοιχα μαζί με το βαθμό τους.
5. Να περιέχει μία συνάρτηση που θα βρίσκει τις απομονωμένες κορυφές του γραφήματος.
Β) Η μεταβατική κλειστότητα (transitive closure) ενός γραφήματος είναι ένας πίνακας R με περιεχόμενα 0 και 1 τέτοιος ώστε R[i,j]=1 μόνον εάν υπάρχει κάποιο μονοπάτι (σύνδεση) μεταξύ των κορυφών i και j του γραφήματος. Σε διαφορετική περίπτωση, R[i,j]=0. Ένας αλγόριθμος για τον υπολογιστή της μεταβατικής κλειστότητας είναι και ο αλγόριθμος Floyd-Warshall:
Είσοδος: Ο πίνακας γειτνίασης Α ενός γραφήματος n κορυφών.
Έξοδος: Ο πίνακας R της μεταβατικής κλειστότητας του γραφήματος.
/* Η αρίθμηση των κορυφών είναι 1,Κ , n. */
R<- A/* Πρώτα αντιγράφουμε τον πίνακα Α στον πίνακα R. */
ΓΙΑ k=1 ΕΩΣ n ΕΠΑΝΕΛΑΒΕ
ΓΙΑ i=1 ΕΩΣ n ΕΠΑΝΕΛΑΒΕ
ΓΙΑ j=1 ΕΩΣ n ΕΠΑΝΕΛΑΒΕ
ΕΑΝ R[i,k]=1 ΚΑΙ R[k,j]=1 ΤΟΤΕ R[i.j]<-1
Υλοποιήστε τον πιο πάνω αλγόριθμο με μία συνάρτηση που δέχεται ως είσοδο δύο πίνακες, Α (πίνακας γειτνίασης) και R (όπου θα επιστρέφεται η έξοδος). Μετά την εκτέλεση της συνάρτησης, ο πίνακας R θα πρέπει να περιέχει τη μεταβατική κλειστότητα του γραφήματος με πίνακα γειτνίασης Α. Δώστε, επίσης, και μία εκτίμηση της πολυπλοκότητας του αλγόριθμου σας ως συνάρτηση του αριθμού των κορυφών του γραφήματος.
Για να ελέγξετε τις απαντήσεις σας στο Α και στο Β πιο πάνω, χρησιμοποιήστε ως είσοδο το γράφημα-παράδειγμα που δίνεται στην εκφώνηση της υποεργασίας.

ethnikos
Δημοσιεύσεις: 39
Εγγραφή: 03 Μαρ 2006 15:13

Γράφημα

Δημοσίευση από ethnikos » 05 Μαρ 2006 11:13

Opios den borei olokliri tin askisi as lisi mono ena meros tis....please einai poli simandiko

Απάντηση

Επιστροφή στο “C, C++”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες