szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 27 maja 2017, o 00:17 
Użytkownik

Posty: 4
Lokalizacja: MZA
Dość logiczne, wynikające z definicji stwierdzenie, jednak nie mam pojęcia jak to można udowodnić. Gdyby ktoś umiał to zrobić to piszcie :)

Treść zadania:
Udowodnij, że izomorfizm grafów zachowuje stopień wierzchołka.
Góra
Mężczyzna Offline
PostNapisane: 27 maja 2017, o 01:26 
Użytkownik
Avatar użytkownika

Posty: 406
Lokalizacja: Warszawa
Wskazówka: izomorfizm zachowuje relację sąsiedztwa.
Góra
Mężczyzna Offline
PostNapisane: 27 maja 2017, o 09:00 
Użytkownik

Posty: 4
Lokalizacja: MZA
Wciąż nie mam pojęcia jak to zrobić. Dużo łatwiej będzie jak napiszesz jak powinien wyglądać taki dowód :)
Góra
Mężczyzna Offline
PostNapisane: 27 maja 2017, o 10:07 
Użytkownik
Avatar użytkownika

Posty: 406
Lokalizacja: Warszawa
Ustal dwa izomorficzne grafy f \colon G_1 \cong G_2 i wybierz w pierwszym z nich wierzchołek. Ma on jakichś sąsiadów v_1, v_2, \ldots, v_n. Co powiesz o f(v_1), f(v_2), \ldots, f(v_n)?
Góra
Mężczyzna Offline
PostNapisane: 27 maja 2017, o 10:25 
Użytkownik

Posty: 4
Lokalizacja: MZA
Ja rozumiem, że tak jest ale nie mam pojęcia jak to udowodnić.f(v_{n}) będzie odpowiadać wierzchołkowi v_{n}. (tzn. będzie miał takich samych sąsiadów, wierzchołki grafu G_{1} odpowiadają wierzchołkom grafu G_{2} w sensie, że gdyby usunąć oznaczenia wierzchołków,
to grafy są takie same)
Góra
Mężczyzna Offline
PostNapisane: 27 maja 2017, o 12:22 
Użytkownik
Avatar użytkownika

Posty: 406
Lokalizacja: Warszawa
No właśnie... więc skoro w pierwszym grafie jest n sąsiadów: \{v_i : i \le n\}, zaś w drugim też: \{f(v_i) : i \le n\}, to stopień został zachowany.
Góra
Mężczyzna Offline
PostNapisane: 27 maja 2017, o 12:37 
Użytkownik

Posty: 4
Lokalizacja: MZA
Tak, tylko tak jak już napisałem wcześniej nie potrafię formalnie zapisać tego dowodu.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Teoria grafów - n kostka  contact  1
 Równanie i dowód  armagonis  2
 Graf hamiltonowski - dowód  piotrekgym  3
 Dowód na nie istnienie danego grafu  tomek1172  1
 Liczba nieizomorficznych grafów o zadanych właściwościach  achr  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl