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.
Dowód zachowania stopnia wierzchołka w izomorfizmie grafów
Re: Dowód zachowania stopnia wierzchołka w izomorfizmie graf
Wciąż nie mam pojęcia jak to zrobić. Dużo łatwiej będzie jak napiszesz jak powinien wyglądać taki dowód
- Cytryn
- 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
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)}\)?
Re: Dowód zachowania stopnia wierzchołka w izomorfizmie graf
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)
to grafy są takie same)
- Cytryn
- 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
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.
Re: Dowód zachowania stopnia wierzchołka w izomorfizmie graf
Tak, tylko tak jak już napisałem wcześniej nie potrafię formalnie zapisać tego dowodu.