Teoria Grafurilor in probleme si aplicatii - Probleme propuse (Cap. 2) - Teoria Grafurilor

Extras din document

Teoria Grafurilor in probleme si aplicatii - Probleme propuse 1.Care dintre urmatoarele afirmatii sunt adevrate si care sunt false: a) Orice marsrut închis contine un ciclu elementar. b) Un marsrut închis de lungime impar contine un ciclu elementar. c) Reuniunea a doua lanturi elementare diferite, ce unesc doua vârfuri ale unui graf contine un ciclu elementar. 2. De construit un graf cu n 2 vârfuri ( ) 3  n , în care valenta oricrui vârf este trei si nu contine cicluri elementare de lungimea trei (triunghiuri). 3.De demonstrat, ca daca un graf G nu este conex, atunci graful complementar este conex. 4.Care este numarul maxim de muchii într-un graf cu n vârfuri, ce nu contine cicluri elementare de lungime par? 5.Care este numrul maxim de muchii într-un graf cu n vârfuri, ce nu conine cicluri elementare? ...