[Marmite]

Ej, panocki, mam pytanie co do tw. Havla o ciągach graficznych - nie ma tego w algorytmie, ale domyslam się, że jeśli pierwszy wyraz ciągu > długość ciągu - 1, to ciąg nie jest graficzny, mam rację? #matematyka #grafy EDIT: czy raczej oznacza to, że na pewno jest graficzny, bo przecież krawędzie mogą prowadzić od wierzchołka do tego samego wierzchołka?

[stefan_pompka]

@Marmite: warunkiem graficzności jest by d1 <= n-1, gdzie d1 to pierwszy wyraz ciągu a n długość ciągu

[stefan_pompka]

@Marmite: a w ogóle to masz http://www.deltami.edu.pl/temat/informatyka/algorytmy/2011/11/01/Odtwarzanie_grafu/

[Marmite]

@stefan_pompka: Okej, dzięki. Nie doczytałem, że twierdzenie Havla odnosi się do grafów prostych tylko :)

[Marmite]

@stefan_pompka: Dzieki za link, ale uczyc się już nie mam czasu - egzamin jutro, przepisuję wszystko co się da do notatek, które mogę mieć ze sobą.

[stefan_pompka]

@Marmite: http://kaims.pl/~deren/ag/wyklady/01_wprowadzenie.pdf przepisuj !

[Marmite]

@stefan_pompka: No właśnie z tego przepisuję ;) już tylko zostały mi liczby chromatyczne i te wszystkie NP problemy.