Ilość nieizomorficznych grafów dwudzielnych

zenek11 · Post autor: **zenek11** » 22 maja 2016, o 15:14

Ile jest wszystkich nieizomorficznych grafów dwudzielnych o czterech wierzchołkach?

Zastanawia mnie czy graf dwudzielny musi być spójny? Nigdzie nie mogę znaleźć odpowiedzi na to pytanie. Jeżeli musi, to według mnie są tylko trzy takie grafy.

Z góry dziękuje za pomoc.

Mruczek · Post autor: **Mruczek** » 3 wrz 2016, o 16:50

Graf dwudzielny nie musi być spójny. Graf jest dwudzielny gdy można pokolorować jego wierzchołki na dwa kolory (czyli podzielić je na dwie grupy) że każde dwa wierzchołki jednego koloru (z jednej grupy) nie mają wspólnej krawędzi.
Ja naliczyłem przynajmniej ze 7:
bez krawędzi, z jedną krawędzią, z dwoma krawędziami (o wspólnym wierzchołku lub nie), z trzema krawędziami (o wspólnym wierzchołku lub ścieżka trzywierzchołkowa), o czterech wierzchołkach (cykl).