Seria 5.
1. Narysuj wszystkie grafy spójne o 4 w złach i 4 wierzchołkach.
010 000
2. Dla grafów z poni szego rysunku
zaznacz ka dy z podzbiorów V1 i V2
podziału zbioru V(G).
110
100
11 00
10 00
111
101
10 01
11 01
011 001
3. Dopełnieniem grafu G nazywamy graf maj cy zbiór wierzchołków V(G) i maj cy kraw d mi dzy wierzchołkami v i w, je li graf G nie ma kraw dzi ł cz cej v i w.
a) Narysuj dopełnienie grafu z rysunku.
b) Ile składowych ma znaleziony graf
dopełniaj cy.
c) Czy je eli graf jest grafem spójnym to
jego dopełnienie jest grafem spójnym?
4. Znajd wszystkie drzewa maj ce 7 wierzchołków. (Odp. jest ich 11).
5. We my drzewo o n wierzchołkach. Ma ono dokładnie n-1 kraw dzi, wi c suma stopni jego wierzchołków wynosi 2n-2.
a) Pewne drzewo ma dwa wierzchołki stopnia 4, jeden wierzchołek stopnia 3 i jeden wierzchołek stopnia 2. Je li inne wierzchołki s stopnia 1, to ile wierzchołków jest w tym grafie? Wskazówka: je li drzewo ma n wierzchołków, to n-4 z nich b d miały stopie 1.
b) Narysuj drzewo opisane w punkcie a).
Z. Doma ski