Narysuj wszystkie grafy o 6 wierzchołkach (izomorficzne)

[Helliocik]

Hej,

Jak w tytule, muszę narysować wszystkie drzewa o 6 wierzchołkach z dokładnością do izomorfizmu.
Znam definicje izomorfizmu, ale średnio mi to pomaga.

Jak narysować pierwsze drzewo do którego, będę rysował dalsze?

Czy jestem w stanie z góry powiedzieć ile ich będzie?

[kerajs]

Drzewa to grafy spójne bez cykli.
Drzew których szukasz jest 6, ale nie wiem czy można z góry określić ich ilość.

[leg14]

To grafy, czy drzewa? bo to spora roznica...

[Helliocik]

pomyłka faktycznie, już poprawiłem-- 16 wrz 2018, o 21:33 --Kerajs, jesteś mi je w stanie pokazać, bądź powiedzieć jak je tworzyć?

[kerajs]

Po prostu je rysujesz:

\(\displaystyle{ \begin{tikzpicture}
\draw[blue](0,0)--(0,2)--(2,2)--(2,0);
\draw[blue](7,0)--(5,1)--(5,2)--(7,2)--(7,1);
\draw[blue](5,0)--(5,1));
\draw[blue](12,0)--(10,0)--(10,2)--(12,2);
\draw[blue](12,1)--(10,1);

\fill (0,0)circle (0.1);
\fill (0,1)circle (0.1);
\fill (0,2)circle (0.1);
\fill (2,2)circle (0.1);
\fill (2,0)circle (0.1);
\fill (2,1)circle (0.1);
\fill (5,0)circle (0.1);
\fill (5,1)circle (0.1);
\fill (5,2)circle (0.1);
\fill (7,0)circle (0.1);
\fill (7,1)circle (0.1);
\fill (7,2)circle (0.1);
\fill (10,0)circle (0.1);
\fill (10,1)circle (0.1);
\fill (10,2)circle (0.1);
\fill (12,0)circle (0.1);
\fill (12,1)circle (0.1);
\fill (12,2)circle (0.1);
\end{tikzpicture}}\)


\(\displaystyle{ \begin{tikzpicture}
\draw[blue](0,0)--(0,2)--(2,2);
\draw[blue](2,0)--(0,2)--(2,1);
\draw[blue](5,0)--(5,2)--(5,1)--(7,1)--(7,0)--(7,2);
\draw[blue](10,0)--(10,2)--(10,1)--(12,1);
\draw[blue](12,0)--(10,1)--(12,2);

\fill (0,0)circle (0.1);
\fill (0,1)circle (0.1);
\fill (0,2)circle (0.1);
\fill (2,2)circle (0.1);
\fill (2,0)circle (0.1);
\fill (2,1)circle (0.1);
\fill (5,0)circle (0.1);
\fill (5,1)circle (0.1);
\fill (5,2)circle (0.1);
\fill (7,0)circle (0.1);
\fill (7,1)circle (0.1);
\fill (7,2)circle (0.1);
\fill (10,0)circle (0.1);
\fill (10,1)circle (0.1);
\fill (10,2)circle (0.1);
\fill (12,0)circle (0.1);
\fill (12,1)circle (0.1);
\fill (12,2)circle (0.1);
\end{tikzpicture}}\)

[Helliocik]

W notatkach z wykładu mam coś takiego
"izomorfizm grafów zachowuje wszystkie cechy grafu, tj. liczbę wierzchołków, liczbę krawędzi, liczbę krawędzi wielokrotnych, liczbę pętli, stopnie wierzchołków.


Szczególnie zastanawia to ostatnie - Stopnie wierzchołków.

Bo np. w grafie 1 mamy:
4 x 2 stopnia
2 x 1 stopnia.

a w grafie drugim już mamy wierzchołek stopnia 3.

I czy to nadal jest izomorfizm?

[kerajs]

muszę narysować wszystkie drzewa o 6 wierzchołkach z dokładnością do izomorfizmu.

z dokładnością do izomorfizmu oznacza, że wszystkie izomorficzne drzewa traktujesz jak jedno. (np. pierwszy graf można poetykietować na 360 sposobów, czyli jest dokładnie tyle izomorficznych grafów, które traktujesz jak jeden graf co do izomorfizmu)

Cytowane polecenie można sformułować też tak: Narysuj wszystkie nieizomorficzne 6-cio wierzchołkowe drzewa.

[leg14]

Proponuję poczytać o tw. Cayley'a (i jego dowód przejrzeć o tam masz algorytm wypisywania wszystkich drzew (przynajmniej w pewnej wersji dowodu)) -

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Cayley%27s_formula