Graf - matematyka dyskretna

[DanteStormdark]

Witam
Poszukuję grafu [matematyka dyskretna], który ma zawierać dwa "mosty" oraz dwa "wierzchołki rozspajające". Potrafię narysować graf z dwoma mostami, jednak taki ma automatycznie powyżej dwóch wierzchołków rozspajających. Może ktoś podać mi przykład swojego grafu z tymi dwoma założeniami?

[Zordon]

Więc sam widzisz, że nie ma takiego grafu, bo mając dwa mosty, musi mieć przynajmniej 3 wierzchołki rozspajające.

[ravgirl]

Niekoniecznie. Może np. tak: . Na kolorowo wierzchołki rozspajające i mosty.

[Zordon]

Masz rację, błędem było przyjęcie, że oba końce mostu są punktami artykulacji.

[DanteStormdark]

Niekoniecznie. Może np. tak: . Na kolorowo wierzchołki rozspajające i mosty.

wow - genialne w swojej prostocie. Tego potrzebowałem, już wiem jak konstruować inne grafy.

____________________________________________________________

Kontynuując wątek o grafie, mam pytanie: jak pokazać, że w grafie hamiltonowskim nie może istnieć wierzchołek rozspajający? Ma ktoś jakiś pomysł jak to rozsądnie udowodnić / pokazać?

[ravgirl]

Nie zauważyłam kolejnego pytania.
Zależy jak zdefiniujemy graf hamiltonowski - czy posiada on ścieżkę, czy też cykl Hamiltona.
Domyślam się, że chodzi o cykl, bo w przypadku pierwszym jest to nieprawda. Wystarczy więc pokazać, że po usunięciu dowolnego wierzchołka wciąż istnieje ścieżka pomiędzy dwoma dowolnymi wierzchołkami w pozostałym grafie.

[DanteStormdark]

Nie zauważyłam kolejnego pytania.
Zależy jak zdefiniujemy graf hamiltonowski - czy posiada on ścieżkę, czy też cykl Hamiltona.
Domyślam się, że chodzi o cykl, bo w przypadku pierwszym jest to nieprawda. Wystarczy więc pokazać, że po usunięciu dowolnego wierzchołka wciąż istnieje ścieżka pomiędzy dwoma dowolnymi wierzchołkami w pozostałym grafie.

Po dłuższej medytacji nad tą wypowiedzą, udało mi się zrozumieć kilka spostrzeżeń z grafami Hamiltona i Eulera. Wielkie dzięki.

________ ____________ ___________ ____________
Kontynuując wątek grafów mam kolejne pytanie: jeżeli istnieją macierze, które reprezentują odległości pomiędzy krawędziami pewnego grafu skierowanego o 8 wierzchołkach. Np takie:

N 12 13 18 19 8 N N
15 N 5 13 1 N 19 N
20 12 N 14 7 N N 1
11 18 7 N 15 3 13 16
10 6 9 19 N 9 15 17
1 N N 17 11 N 1 12
N 10 N 16 7 16 N 7
N N 12 19 14 18 5 N

gdzie N to \(\displaystyle{ \infty}\)
to jak można znaleźć w tym grafie najkrótszą drogę pomiędzy pierwszym i ostatnim wierzchołkiem wykorzystując algorytm Dijkstry?

Chodzi mi o podsunięcie samego sposobu rozwiązania takiego zadania, sam chciałbym to zrobić ale nie wiem jak się zabrać?

[ravgirl]

Chyba nie bardzo rozumiem problem... Algorytm Dijkstry polega ogólnie na poprawianiu przyjętych ograniczeń na długość ścieżki od startowego wierzchołka do pozostałych. Dokładniejszy opis z przykładem, z wykorzystaniem macierzy wag, np. tutaj:

Kod: Zaznacz cały

http://www.algorytm.org/algorytmy-grafowe/algorytm-dijkstry.html

.

[DanteStormdark]

Chyba nie bardzo rozumiem problem... Algorytm Dijkstry polega ogólnie na poprawianiu przyjętych ograniczeń na długość ścieżki od startowego wierzchołka do pozostałych. Dokładniejszy opis z przykładem, z wykorzystaniem macierzy wag, np. tutaj:

Kod: Zaznacz cały

http://www.algorytm.org/algorytmy-grafowe/algorytm-dijkstry.html

.

To jest dokładnie to, czego szukałem. Po raz kolejny wielkie dzięki. Myślę, że już prawie, prawie rozumiem grafy.


---------------------------------
Kontynuując wątek o grafach, mam kolejne pytanie: Czy istnieje metoda, by rzucić okiem na dany graf i wywnioskować na podstawie jego wyglądu, że istnieje [albo nie istnieje] bijekcja w danym grafie? Innymi słowy jak sprawdzić, czy dany graf jest izomorficzny? Nurtuje mnie to niezmiernie.

[ravgirl]

Takiej szybkiej i uniwersalnej metody nie ma. Dla małych grafów można próbować "na oko", ale dla większych jest trudniej. Są też pewne algorytmy dla konkretnych rodzajów grafów, jak drzewa.
Grafy izomorficzne muszą mieć taką samą strukturę - odpowiadające sobie wierzchołki, krawędzie... Można próbować wykluczać istnienie bijekcji, sprawdzając poszczególne cechy grafu, jak liczbę wierzchołków, krawędzi, stopnie wierzchołków itp.

Kod: Zaznacz cały

http://www.algorytm.org/klasyczne/grafy-i-ciag-dalszy.html

(koniec strony)

[DanteStormdark]

Czyli odnośnie tego linku z wikipedii, jeżeli w pokazanym tam grafie H przeprowadzę cięcie z góry na dół dokładnie przez środek, to lewa strona będzie odwzorowaniem prawej strony? Czy dobrze myślę?

... hism_b.svg

[ravgirl]

Nie... czemu mielibyśmy przecinać graf? Problem sprawdzenia czy dane dwa grafy są izomorficzne polega na sprawdzeniu czy mają taką samą strukturę (wierzchołki, krawędzie itd.), czy da się przekształcić jeden w drugi. Można sobie wyobrażać, że w jednym grafie przesuwamy wierzchołki tak, żeby wyglądał jak drugi badany - i jeśli się nie da, to nie są one izomorficzne. Słowem - dwa grafy są izomorficzne, gdy da się je narysować tak, że wyglądają tak samo (gdy można pokazać, że każdy wierzchołek w pierwszym grafie ma swój odpowiednik w drugim).
Co do linku: ten graf to jeden z dwóch. Obok w tabelce jest graf \(\displaystyle{ G}\). Grafy \(\displaystyle{ H}\) i \(\displaystyle{ G}\) są izomorficzne - obok zostało pokazane, który wierzchołek w grafie \(\displaystyle{ G}\) odpowiada któremu wierzchołkowi w grafie \(\displaystyle{ H}\) (swoją drogą akurat w tym przykładzie jest kilka możliwości takiego przypisania). Można sobie wyobrażać taką animację, jak wierzchołki przesuwają się, i z jednego grafu powstaje drugi.

Więcej obrazkowych przykładów:

[DanteStormdark]

Ok, czyli podstawowe prawo które zauważam, to takie, że dwa grafy by były izomorficzne muszą mieć tyle samo wierzchołków. Ilość krawędzi może się różnić. Natomiast samo sprawdzenie tego to po prostu "przeobrażenie" jeden graf w drugi zachowując tylko ilość wierzchołków.

Czy teraz dobrze myślę?

[ravgirl]

Nie tylko ilość wierzchołków musi być taka sama. Także ilość krawędzi, stopnie wierzchołków, zachowanie tego, że jeśli w jednym grafie istnieje krawędź pomiędzy pewną parą wierzchołków, to w drugim istnieje krawędź pomiędzy wierzchołkami im odpowiadającymi. Musi to być identyczna struktura.