Matematyka dyskretna

Seria 5

  1. Narysuj wszystkie grafy spójne o 4 węzłach i 4 wierzchołkach.

0x08 graphic

  1. Dla grafów z poniższego rysunku zaznacz każdy z podzbiorów V1 i V2 podziału zbioru V(G).

  1. 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. 0x08 graphic
    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?

  1. Znajdź wszystkie drzewa mające 7 wierzchołków. (Odp. jest ich 11).

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