THMMY.gr

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

Ένας αλγόριθμος που θα έδινε μια σχετικά καλή λύση, όχι τη βέλτιστη, επιλέγει την ακμή με το μικρότερο βάρος και καταχωρεί τη μια από τις κορυφές που συνδέει στην ομάδα Α και την άλλη στην Β. Στη συνέχεια διαγράφει από το γράφημα τις κορυφές αυτές και επαναλαμβάνει την διαδικασία με τις υπόλοιπες κορυφές. Οι διαδικασία σταματά όταν όλες οι κορυφές του γραφήματος καταχωρηθούν σε κάποια από τις δύο ομάδες.

Να γραφεί το πρόγραμμα το οποίο να υλοποιεί τον πιο πάνω αλγόριθμο. Το πρόγραμμα να εκτυπώνει, για κάθε ομάδα, τις κορυφές που την αποτελούν καθώς και το άθροισμα των βαρών των ακμών που συνδέουν τις κορυφές της ομάδας Α με αυτές της ομάδας Β. Στην περίπτωση που ο αλγόριθμος διαπιστώσει ότι με τη διαδικασία που ακολουθείται δεν καλύφτηκαν όλες οι κορυφές του γραφήματος να τυπώνεται αντίστοιχο μήνυμα. Για την καταχώρηση του γραφήματος οι κορυφές να αριθμούνται από το 0 έως το n-1 (n ο αριθμός των κορυφών του γραφήματος). Στο πρόγραμμα να οριστούν οι πίνακες connection και weight, δύο διαστάσεων. Ο πίνακας connection να ορίζει μια γραμμή για κάθε κορυφή του γραφήματος και να καταχωρεί ως τιμές για τα στοιχεία της γραμμής τους αριθμούς των κορυφών με τις οποίες συνδέεται η κορυφή που αντιστοιχεί στη γραμμή. Ο πίνακας weight να είναι ίδιος με τον πίνακα connection με τη διαφορά ότι αντί για τους αύξοντες αριθμούς των κορυφών, στις ίδιες θέσεις, να καταχωρούνται τα βάρη των ακμών οι οποίες συνδέουν τις κορυφές με την κορυφή στην οποία ανήκει η αντίστοιχη γραμμή του πίνακα.

Σημείωση

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

Για τους πίνακες connection και weight κοιτάξτε το παράδειγμα της άσκησης C.

Ο αλγόριθμος να ελέγχει μόνο ζεύγη κορυφών που συνδέονται μεταξύ τους. Να αγνοεί ζεύγη που δε συνδέονται αν και αυτά θα μπορούσαν να δώσουν καλύτερη λύση.