Question

Arătați: Dacă un graf neorientat cu n > 1 noduri și n-1 muchii nu e conex, are un ciclu.

Answer 1

O sa demonstram negatia propozitiei: Orice Graf cu n noduri, n-1 muchii conex, nu are ciclu Vom folosi urmatorul algoritm pentru a genera un Graf cu n-1 muchii: initial fiecare nod e singur, graful are 0 muchii si sunt n componente conexe(cele n noduri). Vom adauga pe Rand Cate o muchie in graf. Initial sunt n componente conexe(nodurile). Daca la un pas adaugam muchie intre 2 comp conexe diferite, nr de comp conexe scade cu 1. La un pas am forma un ciclu doar daca trasam muchie in aceeasi componenta conexa (Evident). Avand la dispozitie n-1 pasi, si avand in vedere ca trebuie sa ajungem la 1 comp conexa, nu avem voie sa folosim decat pass care unesc 2 comp conexe diferite(altfel nu am avea o comp conexa la final). Dar fiindca mereu adaugam muchie intre 2 comp conexe diferite, Este imposibil sa formam un ciclu. (Daca s-ar forma un ciclu la afaugarea unei muchii a-b, a si b erau in aceeasi componenta conexa de dinainte de muchia respectiva, contradictie). Q.E.D.