Grafy Johnsona

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Apic16
Użytkownik
Użytkownik
Posty: 9
Rejestracja: 23 wrz 2017, o 03:03
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 1 raz

Grafy Johnsona

Post autor: Apic16 »

Witam. Przepraszam ale pewnie nie ten dział ale nie mogłem znaleźć działu dla teorii grafów. Mianowicie mam pytanie : jak tworzy sie grafy Johnsona? Nie mogę znaleźć żadnej strony gdzie jest to dobrze wytłumaczone np. jak wygląda graf \(\displaystyle{ G_{2}(5)}\) , jak się go tworzy?
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Grafy Johnsona

Post autor: kerajs »

1.
Liczysz liczbę wierzchołków : \(\displaystyle{ V= {n \choose k}}\)

Tu: \(\displaystyle{ V= {5 \choose 2} =10}\)

2.
Etykietujesz wierzchołki k-elementowymi kombinacjami liczb ze zbioru n-elementowego: \(\displaystyle{ \left\{ 1,2,3,...,n\right\}}\)

Tu: 10 wierzchołków etykietujesz dwuelementowymi kombinacjami ze zbioru pięcioelementowego : \(\displaystyle{ \left\{ 1,2,3,4,5\right\}}\), co daje 10 wierzchołków o etykietach : \(\displaystyle{ \left\{ (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)\right\}}\)

3.
Jeśli dwa wierzchołki mają w etykietach \(\displaystyle{ k-1}\) takich samych liczb to należy je połączyć krawędzią.

Tu:
Jeśli dwa wierzchołki mają w etykiecie jedną taką samą liczbę to należy je połączyć krawędzią.

Przykładowy wierzchołek z etykietą (1,2) należy połączyć krawędziami z wierzchołkami które w etykietach mają liczbę 1 : \(\displaystyle{ (1,3), (1,4), (1,5)}\) i liczbę 2: \(\displaystyle{ (2,3), (2,4) i (2,5)}\).
Każdy wierzchołek tego grafu jest stopnia 6, a graf ma 30 krawędzi.


Mam nadzieję że instrukcja rysowania grafu jest zrozumiała.


PS

Graf Johnsona J(5,2) jest dopełnieniem grafu Knesera KG(5,2) . Możesz więc go uzyskać przez wymazanie krawędzi grafu Knesera KG(5,2) z grafu pełnego K(10).
Ostatnio zmieniony 30 sty 2019, o 17:36 przez kerajs, łącznie zmieniany 1 raz.
Apic16
Użytkownik
Użytkownik
Posty: 9
Rejestracja: 23 wrz 2017, o 03:03
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 1 raz

Grafy Johnsona

Post autor: Apic16 »

Bardzo Tobie dziękuję. Wszystko zrozumiałem.

-- 30 sty 2019, o 19:10 --

Jeszcze mało pytanko. Czy graf \(\displaystyle{ G_{2}(5)}\) jest hamiltonowski?
Więc z Twierdzenia Orego
\(\displaystyle{ deg(v) + deg(u) \ge n}\) , gdzie \(\displaystyle{ u,v}\) - wierzchołki niepołaczone bezpośrednio
Tak więc u nas \(\displaystyle{ deg(u) = 6}\) i \(\displaystyle{ deg(v)=6}\) i \(\displaystyle{ n=10}\) więc na mocy twierdzenia graf \(\displaystyle{ G_{2}(5)}\) jest hamiltonowski?
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Grafy Johnsona

Post autor: kerajs »

Tak.

Innym podejściem będzie dowód przez okazanie, czyli narysowanie ścieżki (lub cyklu) Hamiltona, co przy takiej mnogości krawędzi nie powinno być problemem.
Np: \(\displaystyle{ (1,2)-(1,3)-(1,4)-(1,5)-(4,5)-(3,5)-(3,4)-(2,3)-(2,4)-(2,5)-(1,2)}\)
ODPOWIEDZ