38ος ΠΔΠ : Κατασκευάζοντας γράφους (constructing) - Λύση

Επεξήγηση εκφώνησης

Σε έναν συνδεδεμένο μη-κατευθυνόμενο γράφο μία κορυφή λέγεται κομβικό σημείο αν αφαιρώντας την ο γράφος δεν είναι πλέον συνδεδεμένος. Αντίστοιχα, μία ακμή λέγεται γέφυρα αν αφαιρώντας την ο γράφος δεν είναι πλέον συνδεδεμένος. Μπορείτε να διαβάσετε περισσότερες πληροφορίες για τα κομβικά σημεία και τις γέφυρες εδώ.

Σε αυτό το πρόβλημα μας ζητείται να φτιάξουμε έναν γράφο με \(N\) κορυφές, \(K\) κομβικά σημεία και \(L\) γέφυρες, ή να αποφανθούμε ότι ένας τέτοιος γράφος δεν υπάρχει.

Παρακάτω θα δούμε όλες τις περιπτώσεις για τις τιμές των \(N, K, L\). Οι ενότητες θα πρέπει να διαβαστούν ως μία μεγάλη if-else πρόταση. Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ.

Περίπτωση \(N = 2\)

Υπάρχει ένας μόνο απλός μη-κατευθυνόμενος γράφος με δύο κορυφές που είναι συνδεδεμένος. Αυτός έχει μία γέφυρα (\(L = 1\)) και κανένα κομβικό σημείο (\(K = 0\)).

Περίπτωση \(K = 0\)

Υποπερίπτωση \(L = 0\)

Γίνεται. Θεωρούμε έναν κύκλο με \(N\) κορυφές. Αυτός δεν έχει κανένα κομβικό σημείο και καμία γέφυρα.

Υποπερίπτωση \(L \geq 1\)

Δεν γίνεται. Εκτός αν \(N = 2\) μία γέφυρα πρέπει να έχει ένα κομβικό σημείο σε ένα από τα δύο της άκρα.

Περίπτωση \(L \geq N\)

Δεν γίνεται. Θεωρούμε τον υπογράφο με μόνο τις γέφυρες. Αυτός έχει τουλάχιστον \(N\) ακμές και το πολύ \(N\) κορυφές, επομένως σχηματίζεται ένας κύκλος μόνο με γέφυρες. Άρα αφαιρώντας οποιαδήποτε από αυτές ο γράφος παραμένει συνδεδεμένος. Άτοπο

Περίπτωση \(K \geq N - 1\)

Δεν γίνεται. Όπως είπαμε παραπάνω, οι \(N - 1\) γέφυρες δημιουργούν ένα δέντρο και το δέντρο πρέπει να έχει τουλάχιστον δύο φύλλα.

Περίπτωση \(L \geq Κ\)

Υποπερίπτωση \(L = N - 2\)

Δεν γίνεται. Σε αυτή την περίπτωση οι \(L\) γέφυρες ορίζουν ένα δέντρο. Η \((N - 1)\)-οστή ακμή πρέπει να μην είναι γέφυρα, επομένως όταν την βάζουμε στον γράφο δημιουργεί έναν κύκλο. Ο κύκλος αυτός θα περιλαμβάνει τα δύο άκρα της ακμής και τουλάχιστον ένα ακόμα. Τουλάχιστον δύο από αυτούς τους τρεις κόμβους συνδέονται και από ένα μονοπάτι στο δέντρο άρα δημιουργείται ένας κύκλος, που περιέχει γέφυρες. Άτοπο.

Υποπερίπτωση (\(L \leq N - 3\))

Γίνεται. Δημιουργούμε μία αλυσίδα με \(K\) κόμβους. Προσθέτουμε στο τέλος έναν κόμβο που δεν είναι κομβικός και στην αρχή ενώνουμε τις \(N - (L-1) \geq 2\) (μη κομβικές) κορυφές σε έναν κύκλο με δύο εισερχόμενες ακμές. Τις υπόλοιπες \(L - (K + 1)\) κορυφές τις ενώνουμε στον πρώτο κόμβο μία προς μία ώστε να δημιουργήσουν τις υπόλοιπες γέφυρες.

Ο παρακάτω κώδικας δημιουργεί αυτόν το γράφο.

      // Φτιάχνουμε ένα μονοπάτι με τα κομβικά σημεία. 
      for (int i = 1; i <= K; ++i) {
         add_edge(i,i+1);
      }
      // Βάζουμε κόμβους συνδεδεμένους μόνο με την πρώτη 
      // κορυφή για να δημιουργήσουμε τις υπόλοιπες γέφυρες.
      int independent_start = K + 2;
      for (int j = 0; j < (L - K); ++j) {
        add_edge(1, independent_start + j);
      }
      // Βάζουμε έναν κύκλο με τις υπόλοιπες κορυφές.
      int non_critical_start = L + 3;
      if (non_critical_start <= N) {
        for (int j = non_critical_start; j <= N; ++j) {
          if (j < N) add_edge(j, j + 1);
          else add_edge(N, non_critical_start);
        }
        add_edge(1, N);
        add_edge(1, non_critical_start);
      }

Περίπτωση (\(L < Κ\))

Υποπερίπτωση \(2 K - L + 3 \leq N\)

Γίνεται. Δημιουργούμε μία αλυσίδα με \(K\) κομβικά σημεία και με μία κορυφή στην αρχή. Στις πρώτες \(L - K\) ακμές προσθέτουμε μία ενδιάμεση κορυφή για να μην είναι πλέον γέφυρες. Τους υπόλοιπους κόμβους τους προσθέτουμε ως κύκλο (θα είναι τουλάχιστον 2) και τους συνδέουμε στην τελευταία κορυφή του μονοπατιού.

Ο παρακάτω κώδικας δημιουργεί αυτόν το γράφο.

      // Βάζουμε όλα τα κομβικά σημεία σε ένα μονοπάτι
      // και μία κορυφή στο τέλος.
      for (int i = 1; i <= K; ++i) {
        add_edge(i, i + 1);
      }
      // Βάζουμε ενδιάμεσες κορυφές, ώστε οι K - L ακμές του
      // μονοπατιού να μην είναι πλέον γέφυρες.
      int intermmediate_nodes_start = K + 2;
      for (int j = 0; j < (K - L); ++j) {
        add_edge(j + 1, intermmediate_nodes_start + j);
        add_edge(j + 2, intermmediate_nodes_start + j);
      }
      // Προσθέτουμε έναν κύκλο με τις υπόλοιπες κορυφές που δεν 
      // είναι κομβικές.
      int non_critical_nodes_start = 2*K - L + 2;
      add_edge(K+1, non_critical_nodes_start);
      for (int j = non_critical_nodes_start; j < N; ++j) {
        add_edge(j, j + 1);
      }
      if (non_critical_nodes_start < N) add_edge(N, K+1);

Υποπερίπτωση \(2 K - L + 3 > N\)

Δεν γίνεται. Η απόδειξη προκύπτει από το γεγονός ότι οι δινσυνδετικές συνιστώσες του γράφου δημιουργούν ένα δέντρο. Οι γέφυρες ενώνουν διαφορετικές συνιστώσες με μονοπάτια, επομένως αφαιρώντας τις λαμβάνουμε ένα δέντρο με \(L\) λιγότερες συνιστώσες. Στο υπόλοιπο δέντρο κάθε εσωτερική συνιστώσα χρειάζεται τουλάχιστον μία μη-κομβική κορυφή, ενώ κάθε φύλλο χρειάζεται τουλάχιστον δύο. Δηλαδή συνολικά χρειαζόμαστε τουλάχιστον \(2\cdot (\text{φύλλα}) + 1 \cdot (\text{εσωτερικά})\) μη-κομβικές κορυφές, δηλαδή \(2\cdot (\text{φύλλα}) + 1 \cdot (\text{εσωτερικά}) + K\) κορυφές συνολικά.

Κάθε δέντρο πρέπει να έχει τουλάχιστον δύο φύλλα άρα χρειαζόμαστε τουλάχιστον

κορυφές. Επομένως, με λιγότερες δεν γίνεται.

Συνδυάζοντας αυτές τις περιπτώσεις περνάει όλα τα testcases. Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ.