O dwóch ciekawych problemach grafowych

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ń.