szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 29 sie 2009, o 16:20 
Użytkownik

Posty: 31
Lokalizacja: Gumiland
Wyznacz wzór dla grafu L(G) w zależności od stopni wierzchołków grafu G.
Automorfizm. Proszę o rysunek grafów pełnych K _{4} oraz K_{5} wraz z ich grupami automorfizmów.

Pozdrawiam.
Góra
Mężczyzna Offline
PostNapisane: 29 sie 2009, o 23:35 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
Pierwsze zadanie akurat robiłem dziś na korepetycjach:

Oznaczmy wierzchołki grafu G przez v_1,v_2, \dots , v_n. Weźmy dowolny wierzchołek v_i i zauważmy, że jest on końcem deg(v_i) krawędzi grafu G. Każda z tych krawędzi staje się wierzchołkiem w grafie krawędziowym L(G), a co więcej każde takie dwa wierzchołki w L(G) są połączone krawędzią generowaną przez v_i. Zatem ów wierzchołek generuje { deg(v_i) \choose 2} krawędzi. W sumie więc w grafie krawędziowym L(G) mamy:
\sum_{i=1}^{n} { deg(v_i) \choose 2} krawędzi.

Można jeszcze pokazać (wykorzystując lemat o uściskach dłoni), że ten wzór da się przekształcić do:
-m + \frac{1}{2} \sum_{i=1}^{n}  deg(v_i)^2
gdzie m jest liczbą krawędzi grafu G.

Q.
Góra
Mężczyzna Offline
PostNapisane: 10 lip 2015, o 15:00 
Użytkownik

Posty: 541
Lokalizacja: Kielce
A co w sytuacji gdy mamy wierzchołek stopnia 1 wtedy otrzymamy symbol Newtona {1 \choose 2} i w jaki sposób otrzymać tamten wzór z lematu o usciskach?
Góra
Mężczyzna Offline
PostNapisane: 10 lip 2015, o 16:30 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
Wierzchołek stopnia 1 w grafie G nie generuje żadnej krawędzi w grafie L(G) i zgadza się to z tym, że \binom 12 = 0.

A drugi wzór wynikający z lematu o uściskach dłoni nie ma związku z powyższą uwagą, tam są tylko rachunki.

Q.
Góra
Mężczyzna Offline
PostNapisane: 10 lip 2015, o 22:38 
Użytkownik

Posty: 541
Lokalizacja: Kielce
Chodziło mi o to jak się definiuje ten symbol Newtona bo nie wiedziałem że jest równy zero . Mam jeszcze pytanie pdf topic. Czy w grafie dwudzielnym mogą być punkty izolowane?
Góra
Mężczyzna Offline
PostNapisane: 23 lip 2015, o 08:09 
Gość Specjalny

Posty: 3051
Lokalizacja: Gołąb
Tak. Dlaczego niby nie miałoby to być możliwe?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 ilość pieciocyfrowych kombinacji  strefa61  4
 Ilość słów  alla2012  1
 Ilość liczb z niemalejącym ciągiem cyfr  vtvs  5
 Ilość możliwości rozwiązania Sudoku  darek88  2
 Ilośc rozwiązań równań i nierówności w liczbach naturalnych.  Luxxar  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl