Witam
Potrzebuję napisać algorytm do sprawdzenia czy dany graf jest mapą. Przydałoby mi się kilka własności map grafowych. Niestety google niezbyt konkretnie odpowiada na moje zapytania. Dlatego pytam Was, jakie własności ma mapa, najlepiej żeby była to własność "wtedy i tylko wtedy" ale każda inna też jest mile widziana.
Od prowadzącego zajęcia dostałem takie 4 podpunkty ale uważam, że ich sprawdzenie nie jest wystarczające lub jest niewłaściwe:
* graf musi być planarny
* graf musi być 3-spójny
* graf nie zawiera rozcięć mających 1 lub 2 krawędzie.
* graf nie posiada wierzchołków stopnia 1 lub 2
Np zwykły trójkąt (graf pełny, nieskierowany, o 3 wierzchołkach) jest mapą a jednak wg wskazówek prowadzącego nie jest Ot taki zonk...
Pozdrawiam