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?
Grafy
-
- Użytkownik
- Posty: 185
- Rejestracja: 6 maja 2006, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Pomógł: 32 razy
Grafy
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)
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)