O dwóch ciekawych problemach grafowych

Speaker(s)

Krzysztof Diks

Affiliation

Uniwersytet Warszawski

Date

Nov. 25, 2004, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

Opowiemy o dwóch znanych problemach grafowych postawionych ogólniej niż się to robi klasycznie. Przedstawimy ugólnione twierdzenie Vizinga o kolorowaniu krawędzi multigrafu i pokażemy, w jaki sposób znajdować cykle Eulera w grafach mieszanych, tzn. takich, w których mogą się pojawiać zarówno krawędzie skierowane, jak i nieskierowane. W naszych rozważaniach skoncentrujemy się na algorytmicznych aspektach omawianych zagadnień.

---