Θεωρία Γράφων

[Debugging_Daemon]

Καλησπέρα. Γνωρίζουμε ότι σε έναν γράφο G=(V,E) το κ(G) είναι το ελάχιστο πλήθος κορυφών που πρέπει να αφαιρεθούν για να προκύψει μη συνεκτικός γράφος. Αν έχω βρει ένα σύνολο κορυφών που αν αφαιρεθούν ο γράφος που προκύπτει είναι μη συνεκτικός, πως γνωρίζω ότι είναι οι ελάχιστες κορυφές σε αριθμό χωρίς να εξετάσω όλα τα υποσύνολα του V?

 

[41%]

το ελάχιστο πλήθος κορυφών που πρέπει να αφαιρεθούν για να προκύψει μη συνεκτικός γράφος

AN N κορυφές τότε απαιτούνται τουλάχιστον N-1 ακμές για να είναι συνεκτικός, στις Ν-2 δεν μπορεί να είναι.