Dowód zachowania stopnia wierzchołka w izomorfizmie grafów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Renq77
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 26 maja 2017, o 23:46
Płeć: Mężczyzna
Lokalizacja: MZA

Dowód zachowania stopnia wierzchołka w izomorfizmie grafów

Post autor: Renq77 »

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.
Awatar użytkownika
Cytryn
Użytkownik
Użytkownik
Posty: 405
Rejestracja: 17 wrz 2016, o 17:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 2 razy
Pomógł: 46 razy

Re: Dowód zachowania stopnia wierzchołka w izomorfizmie graf

Post autor: Cytryn »

Wskazówka: izomorfizm zachowuje relację sąsiedztwa.
Renq77
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 26 maja 2017, o 23:46
Płeć: Mężczyzna
Lokalizacja: MZA

Re: Dowód zachowania stopnia wierzchołka w izomorfizmie graf

Post autor: Renq77 »

Wciąż nie mam pojęcia jak to zrobić. Dużo łatwiej będzie jak napiszesz jak powinien wyglądać taki dowód
Awatar użytkownika
Cytryn
Użytkownik
Użytkownik
Posty: 405
Rejestracja: 17 wrz 2016, o 17:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 2 razy
Pomógł: 46 razy

Re: Dowód zachowania stopnia wierzchołka w izomorfizmie graf

Post autor: Cytryn »

Ustal dwa izomorficzne grafy \(\displaystyle{ f \colon G_1 \cong G_2}\) i wybierz w pierwszym z nich wierzchołek. Ma on jakichś sąsiadów \(\displaystyle{ v_1, v_2, \ldots, v_n}\). Co powiesz o \(\displaystyle{ f(v_1), f(v_2), \ldots, f(v_n)}\)?
Renq77
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 26 maja 2017, o 23:46
Płeć: Mężczyzna
Lokalizacja: MZA

Re: Dowód zachowania stopnia wierzchołka w izomorfizmie graf

Post autor: Renq77 »

Ja rozumiem, że tak jest ale nie mam pojęcia jak to udowodnić.\(\displaystyle{ f(v_{n})}\) będzie odpowiadać wierzchołkowi \(\displaystyle{ v_{n}}\). (tzn. będzie miał takich samych sąsiadów, wierzchołki grafu \(\displaystyle{ G_{1}}\) odpowiadają wierzchołkom grafu \(\displaystyle{ G_{2}}\) w sensie, że gdyby usunąć oznaczenia wierzchołków,
to grafy są takie same)
Awatar użytkownika
Cytryn
Użytkownik
Użytkownik
Posty: 405
Rejestracja: 17 wrz 2016, o 17:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 2 razy
Pomógł: 46 razy

Re: Dowód zachowania stopnia wierzchołka w izomorfizmie graf

Post autor: Cytryn »

No właśnie... więc skoro w pierwszym grafie jest \(\displaystyle{ n}\) sąsiadów: \(\displaystyle{ \{v_i : i \le n\}}\), zaś w drugim też: \(\displaystyle{ \{f(v_i) : i \le n\}}\), to stopień został zachowany.
Renq77
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 26 maja 2017, o 23:46
Płeć: Mężczyzna
Lokalizacja: MZA

Re: Dowód zachowania stopnia wierzchołka w izomorfizmie graf

Post autor: Renq77 »

Tak, tylko tak jak już napisałem wcześniej nie potrafię formalnie zapisać tego dowodu.
ODPOWIEDZ