Grafy
: 07 wrz 2015, 01:46
Witam,
Mam problem ze zrozumieniem zadania.
Wyznacz odpowiednie parametry zadanych grafów (pamiętaj, że w cyklu wierzchołki nie mogą się powtarzać):
I dla przykładu w podpunkcie a) mam grafy:
\(K_3 + C_8\) i mam podać liczbę chromatyczną, długość najdłuższego cyklu i długość optymalnej trasy chińskiego listonosza. Dwie pierwsze wartości umiem podać, natomiast z trasą chińskiego listonosza mam problem. Nie ma rysunków do zadania, nie ma też nic wspomniane o wagach krawędzi. Skoro nie ma wag, to jak mam wyznaczyć tę trasę? Wrzucam tu link do rozrysowanych grafów i moich odpowiedzi do pierwszego przykładu. Dodam też, że według wykładowcy ta wartość dla chińskiego listonosza powinna wynosić 39, ale jak?
http://sketchtoy.com/65851509
Mam problem ze zrozumieniem zadania.
Wyznacz odpowiednie parametry zadanych grafów (pamiętaj, że w cyklu wierzchołki nie mogą się powtarzać):
I dla przykładu w podpunkcie a) mam grafy:
\(K_3 + C_8\) i mam podać liczbę chromatyczną, długość najdłuższego cyklu i długość optymalnej trasy chińskiego listonosza. Dwie pierwsze wartości umiem podać, natomiast z trasą chińskiego listonosza mam problem. Nie ma rysunków do zadania, nie ma też nic wspomniane o wagach krawędzi. Skoro nie ma wag, to jak mam wyznaczyć tę trasę? Wrzucam tu link do rozrysowanych grafów i moich odpowiedzi do pierwszego przykładu. Dodam też, że według wykładowcy ta wartość dla chińskiego listonosza powinna wynosić 39, ale jak?
http://sketchtoy.com/65851509