szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 6 lut 2015, o 11:29 
Użytkownik

Posty: 1
Lokalizacja: Polska
Witam,

mam takie pytanko odnośnie izomorficzności 2 grafów. Wg notatek z wykładu:
"Dwa grafy G1 i G2 są izomorficzne, jeśli istnieje wzajemnie jednoznaczna odpowiedniość między wierzchołkami grafu G1 i wierzchołkami grafu G2 taka, że liczba krawędzi łączących dowolne dwa wierzchołki w G1 jest równa liczbie krawędzi łączących odpowiadające im wierzchołki w G2."

Mam jedną niejasną kwestię - czy jeżeli przykładowo graf ma KOLEJNO takie wierzcholki X1, X2, X3, X4, X5, a drugi graf Y5, Y3, Y1, Y2, Y4 to ja muszę kolejno każdemu wierzchołkowi dopasować pasujący mu wierzchołek w drugim grafie zgodnie z kolejnością występowania (X1 - Y5, X2 - Y3 itd.)?

Czy wystarczy jeżeli np. wezmę sobie wierzchołek X3 i znajdę taki sam (z liczbą krawędzi do tego wierzchołka) w drugim grafie np. Y1 i zrobię tak dla wszystkich wierzchołków?

Proszę o szybką odpowiedź jeśli to jest możliwe bo zaliczenie poprawkowe już za parę godzin ;/
Góra
Kobieta Offline
PostNapisane: 6 lut 2015, o 12:26 
Użytkownik
Avatar użytkownika

Posty: 2505
Kiedy mówimy o grafach, warto robić rysunki. W tym przypadku chodzi o to, by izomorfizm zachowywał sąsiedztwo, tzn. jeżeli dwa wierzchołki są połączone w G, to są połączone też w G'. Samo zachowywanie stopnia nie wystarczy: spójrz na sześcian (osiem wierzchołków, wszystkie stopnia trzy). Bijekcji jest masa (8!), ale izomorfizmów tylko trochę.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Matematyka dyskretna - teoria grafów  aleheca  7
 Grafy obliczanie wierzchołków. bazy minimalne grafów  marcin2991  0
 Drzewa i liście - teoria grafów  silvaran  1
 Stabilność grafów, tłumaczenie  niusiaa9  3
 Jaka jest liczba minimalnych grafów planarnych, które ...  kylercopeland  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl