Narysuj wszystkie grafy o 6 wierzchołkach (izomorficzne)
Narysuj wszystkie grafy o 6 wierzchołkach (izomorficzne)
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?
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?
Ostatnio zmieniony 16 wrz 2018, o 21:20 przez Helliocik, łącznie zmieniany 1 raz.
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Narysuj wszystkie grafy o 6 wierzchołkach (izomorficzne)
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ść.
Drzew których szukasz jest 6, ale nie wiem czy można z góry określić ich ilość.
Narysuj wszystkie grafy o 6 wierzchołkach (izomorficzne)
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
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Narysuj wszystkie grafy o 6 wierzchołkach (izomorficzne)
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}}\)
\(\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}}\)
Narysuj wszystkie grafy o 6 wierzchołkach (izomorficzne)
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?
"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
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Narysuj wszystkie grafy o 6 wierzchołkach (izomorficzne)
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)Helliocik pisze:muszę narysować wszystkie drzewa o 6 wierzchołkach z dokładnością do izomorfizmu.
Cytowane polecenie można sformułować też tak: Narysuj wszystkie nieizomorficzne 6-cio wierzchołkowe drzewa.
- leg14
- Użytkownik
- Posty: 3132
- Rejestracja: 5 lis 2014, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: Radom
- Podziękował: 154 razy
- Pomógł: 475 razy
Re: Narysuj wszystkie grafy o 6 wierzchołkach (izomorficzne)
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