Inne, zadanie nr 1152
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
sebastian123 post贸w: 22 |  2013-02-28 12:26:49Witam, 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