Doliwa, Seria 7

Zad 1.

1. Jest niespójny, pozostałe są spójne.

2. Nie zawiera żadnego podgrafu, którego krawędzie i wierzchołki tworzą trójkąt. Grafy c, d, e takowe zawierają (np. trzy wierzchołki od góry i łączące je krawędzie).

3. Zawiera dwa podgrafy trójkątne i dwa pięciokątne, graf d zwiera tylko jeden trójkątny, graf e żadnego pięciokątnego.

4. Zawiera jeden podgraf trójkątny, graf e ma 4 takie.

Zad 2.

K2, 3	$$\begin{pmatrix} \begin{matrix} 0 & 0 \\ 0 & 0 \\ \end{matrix} & \begin{matrix} \begin{matrix} 0 & 1 \\ 0 & 1 \\ \end{matrix} & \begin{matrix} 1 \\ 1 \\ \end{matrix} \\ \end{matrix} \\ \begin{matrix} \begin{matrix} 0 \\ 1 \\ \end{matrix} & \begin{matrix} 0 \\ 1 \\ \end{matrix} \\ 1 & 1 \\ \end{matrix} & \begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \\ \end{matrix} \\ \end{pmatrix}$$
1	2
4	5

Zad 3.

a)

b) Graf jest półeulerowski, ponieważ posiada dwa wierzchołki nieparzystego stopnia( 3 i 4). Trasa przechodzi kolejno przez wierzchołki: 3, 5, 2, 1, 3, 4, 1, 4

c) w grafie istnieje cykl Hamiltona, przechodzi kolejno przez wierzchołki: 1, 2, 5, 3, 4, 1