Grafy

[blanka_00]

Będę niezmiernie wdzięczna za pomoc w zrobieniu tego zadanka



Niech G będzie grafem prostym, nieskierowanym, w którym połączenia między wierzchołkami opisuje symetryczna macierz połączeń.

\(\displaystyle{ \begin{tabular}{ccccc}
1&1& 1 & 0 & 0 \\
1 & 0& 0 & 1 & 0\\
1 & 0 & 0 & 0 & 0\\
0 & 1 & 0& 1 &0\\
0 &0& 0 & 0 & 1\\
\end{tabular}}\)

1) Naszkicuj graf G.
2) Czy jest on spójny? (uzasadnij odpowiedź)
3) Czy ma krawędzie wielokrotne? (uzasadnij odpowiedź)
4) Czy jest drzewem? (uzasadnij odpowiedź)
5) Jakie ma stopnie wierzchołków? (uzasadnij odpowiedź)
6) Ile ma krawędzi?
7) Czy jest planarny? (uzasadnij odpowiedź)
8) Czy ma cykle? (uzasadnij odpowiedź)
9) Czy ma cykl Eulera? (uzasadnij odpowiedź)
10) Czy ma drogę Hamiltona? (uzasadnij odpowiedź)
11) Ilu kolorów należy użyć do pokolorowania wierzchołków?
12) Ilu kolorów należy użyć do pokolorowania krawędzi?

[UNIX_admin]

2. nie, poniewaz, po odjeciu maciezy I otrzymamy kolumne/wiersz zerowa
3. tak, sa jedynki symetryczne wzgledem diagonalnej
4. nie, bo nie jest spojny
7. tak, nie zawiera K5 ani K3,3 (maciez nie zawiera podmacierzy)
8. nie, chyba, ze krzwedzie rownolegle lub petle
9. tylko po rownoleglych i petlach skladowej spojnej (wiec odpowiedz raczej na nie)
10. nie, nie jest spojny (skladowa spojna ma)
11 i 12 zalezy jak trakowac rownolegle i petle (petle uniemozliwiaja pokolorowanie wierzcholkow)