1. Narysuj wszystkie grafy spójne o 4 węzłach i 4 wierzchołkach.
2. Dla grafów z poniższego rysunku zaznacz każdy z podzbiorów V1 i V2 podziału zbioru V(G).
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)
c) Ile składowych ma znaleziony graf dopełniający.
d) 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
Minnie_