Vybrané kapitoly z diskrétnej matematiky

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: K₆, K_2,5, W₇

6. Koľko hrán má graf W_n ?

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 K₇?

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?