LISTA ZADA NR 8
1. Zrób rysunki wszystkich 14 grafów o trzech wierzchoªkach i trzech kraw¦dziach.
2. Zrób rysunki wszystkich grafów o czterech wierzchoªkach i czterech kraw¦dziach, które nie maj¡
p¦tli i kraw¦dzi wielokrotnych.
3. Które z grafów z zada« 1 i 2 s¡:.
a) proste
b) acykliczne
c) spójne
d) regularne ?
4. Graf o 21 kraw¦dziach ma 7 wierzchoªków stopnia 1, 3 wierzchoªki stopnia 2, 7 wierzchoªków stopnia 3, a pozostaªe wierzchoªki maj¡ stopie« 4. Ile ma on wierzchoªków?
5. Które z nast¦puj¡cych ci¡gów s¡ ci¡gami liczb wierzchoªków kolejnych stopni grafu (tzn. ilo±¢
wierzchoªkow stopnia 0-wego, 1-wszego, 2-giego, itp.). W ka»dym przypadku albo narysuj graf przykªadowy o danym ci¡gu liczb wierzchoªków kolejnych stopni, albo wyja±nij, dlaczego taki graf nie istnieje:
a) (1, 1, 0, 3, 1, 0, 0,...)
b) (0, 1, 0, 2, 1, 0, 0,...)
c) (0, 0, 2, 2, 1, 0, 0,...)
d) (0, 1, 0, 1, 1, 1, 0,...)
e) (0, 0, 0, 4, 0, 0, 0,...)
6. Narysuj wszystkie grafy, których ci¡g liczb wierzchoªków kolejnych stopni ma posta¢: (0, 2, 1, 2, 0, 0,...)
7. Napisz macierz s¡siedztwa i macierz incydencji wybranych dwóch grafów z zadania 6.
8. Narysuj graf, którego macierz s¡siedztwa ma posta¢:
1 1 0 0 0 0 0 0 0
1 0 1 1 1 0 0 0 0
0 1 0 2 0 0 0 0 0
0 1 2 0 0 0 0 0 0
0 1 0 0 0 2 0 0 0
0 0 0 0 2 0 0 0 0
0 0 0 0 0 0 2 2 0
0 0 0 0 0 0 2 0 1
0 0 0 0 0 0 0 1 0
Grzegorz Kondrat