Wstęp do grafów

W grafie prostym krawędź jest

• Ciągiem wierzchołków

• Zbiorem wierzchołków

• Listą wierzchołków

• Parą wierzchołków

Ile krawędzi ma dopełnienie tego grafu:

• 2

• 3

• 4

• 5

Stopień maksymalny cyklu C^n wynosi

• N

• N-2

• N/2

• 2

Jakiego koloru są dojrzałe jeżyny:

• zielone

• czerwone

• czarne

• żółte

Ile krawędzi należy dodać do ścieżki P^n żeby utworzyć z niej cykl C^n

• 1

• 2

• ze ścieżki P^n nie da się utworzyć cyklu C^n

• n

Ile maksymalnie krawędzi może mieć multigraf na n wierzchołkach

• n po 2

• n razy n po 2

• N^(n po 2)

• Żadna odpowiedź nie jest prawidłowa

Wierzchołek izolowany:

• Nie jest incydenty z żadnym innym wierzchołkiem

• Ma dodatni stopień

• Nie wychodzą z niego żadne krawędzie

• Należy tylko do niespójnych grafów

Dwa grafy izomorficzne

• Maja tyle samo wierzchołków

• Maja tyle samo krawędzi

• Mają tyle samo cykli

• Wszystkie odpowiedzi są prawidłowe

W grafie k-regularnym

• Każda krawędź leży na cyklu długości k

• Każdy wierzchołek ma stopień k

• Każda krawędź występuje k razy (jest to multigraf)

• Dla każdego wierzchołka v istnieje wierzchołek u oddalony o dokładnie k od niego.

Podgraf grafu G

• Musi mieć mniej krawędzi niż graf G

• Zawiera co najmniej jedną krawędź

• Musi mieć tyle samo wierzchołków co graf G

• Może być cyklem