S3: Základné druhy grafov
1. Je možné nakresliť graf s graf, ktorý má 3 vrcholy stupňa 5 a sedem vrcholov stupňa 4?
2. Ukážte, že postupnosť čísel {6,1,3,2,3,2,4,1} je skóre nejakého grafu. Nakreslite aspoň dva neizomorfné diagramy takého grafu.
3. Ukážte,
že postupnosť čísel {1,3,3,3} nie je skóre grafu.
4. Ukážte, že grafy na obrázku sú izomorfné. Pre grafy vpravo označte vrcholy symbolmi resp. tak, aby zobrazenie resp. bol izomorfizmus.
5. Nakreslite diagramy grafov: K6, K2,5, W7
6. Koľko hrán má graf Wn ?
7. Nakreslite diagram pravidelného grafu, ktorý má 8 vrcholov a stupne vrcholov sú rovné 4.
8. Nakreslite
diagramy všetkých 2-pravidelných podgrafov kompletného grafu
K7?
9. Ukážte, že v ľubovoľnom párnom (bipartitnom) grafe neexistuje kružnica nepárnej dĺžky.
10. Napíšte incidenčné matice grafov K1,5 a W5.
11. Ktoré z nasledujúcich tvrdení sú pravdivé?
a. Izomorfné grafy majú rovnaký počet vrcholov.
b. Grafy s rovnakým počtom vrcholov sú izomorfné.
c. Izomorfné grafy majú rovnaký počet hrán
d. Grafy s rovnakým počtom hrán sú izomorfné.
12. Ukážte, že postupnosť čísiel {1,2,3,3,4,5,6} je skóre nejakého grafu. Nakreslite aspoň tri neizomorfné grafy takéhoto grafu.
13. Je možné nakresliť graf s ôsmimi vrcholmi stupňa 5?
14. Popíšte nejaké situácie z praxe, ku ktorým
zodpovedajú navzájom komplementárne grafy?