logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Inne, zadanie nr 1152

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

sebastian123
postów: 22
2013-02-28 12:26:49

Witam, studiuje informatyke i na przyszly kolos mają być grafy. Prosiłbym tylko o wyjaśnienie dwóch przykładów:
1).Jeśli w implementacji przez macierz sąsiedztwa graf nie skierowany G wygląda następująco:

1 2 3 4
1:0 1 0 1
2:0 0 1 0
3:0 1 0 1
4:0 1 0 0
to w G istnieje cykl a) 1,2,3,1 b) 2,3,4,2 c) 3,4,1,3 d) 4,2,1,4.
(która odpowiedz i dla czego ? nie potrafie znalezc wytlumaczenia w internecie ani w wykladach).
2).Jeśli w implementacji przez listy sąsiedztwa graf nieskierowany G wygląda następująco:

1: 2->3->4
2: 1->3
3: 1->2->4
4: 1->3
to można go pokolorować a) jednym b) dwoma c) trzema d) czterema kolorami.
(Jaka odpowiedz i dlaczego ? i jak bedzie sie roznil wynik gdyby graf byl skierowany.).
Pozdrawiam



tumor
postów: 8070
2013-02-28 12:46:10

Przede wszystkim informatyk mógłby użyć latexa. :)

Macierz sąsiedztwa ma 1 tam, gdzie jakieś wierzchołki są połączone krawędzią. W przypadku grafu nieskierowanego połączenie $(1,4)$ i $(4,1)$ jest tym samym (i raczej zapiszemy $\{1,4\}$), zatem macierz powinna być symetryczna względem głównej przekątnej. Nie jest. Albo źle przepisałeś macierz, albo graf jest skierowany, albo pomylił się ktoś inny. ;)

Gdyby graf był skierowany to sprawdzamy.
a) cykl oznacza krawędzie (skierowane) $(1,2),(2,3)(3,1)$
Dwie pierwsze w macierzy widzimy, ale trzeciej nie, czyli odpada
b) $(2,3),(3,4),(4,2)$ - tu wszystkie krawędzie odnajdujemy w macierzy
c) tu w macierzy nie ma $(4,1)$
d) tu w macierzy nie ma $(2,1)$




tumor
postów: 8070
2013-02-28 13:02:55

2) Zauważamy, że $\{1,2,3\}$ jest kliką (podgrafem pełnym, każde dwa z wierzchołków są połączone krawędzią). Muszą być zatem co najmniej 3 kolory.
Wierzchołek 4 nie jest połączony krawędzią z 2, zatem może mieć ten sam kolor. Wystarczą 3 kolory. Oczywiście więcej ich też być może, jeśli kto chce. ;)

Przy grafie skierowanym nie pomogę, chyba że mi napiszesz reguły kolorowania. Jeśli takie same, czyli (x,y) dla żadnej krawędzi skierowanej x,y nie są w jednym kolorze, to odpowiedź będzie jak dla nieskierowanego.


sebastian123
postów: 22
2013-02-28 14:57:51

Dobrze, co nieco zrozumiałem. Dziękuje Ci serdecznie, pomogles mi :)

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt online: 22 drukuj