Matematyka dyskretna

Seria 5

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 V₁ i V₂ 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.

1. Narysuj dopełnienie grafu z rysunku.

2. 
   Ile składowych ma znaleziony graf dopełniający.

3. 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.

1. 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.

2. Narysuj drzewo opisane w punkcie a).

Z. Domański

10 01

11 00

11 01

10 00

011 001

010 000

111

101

110

100

---