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 \(\displaystyle{ K _{4}}\) oraz \(\displaystyle{ K_{5}}\) wraz z ich grupami automorfizmów.
Pozdrawiam.
Wzór na ilość krawędzi oraz automorfizm.
-
- Użytkownik
- Posty: 31
- Rejestracja: 5 maja 2008, o 15:20
- Płeć: Mężczyzna
- Lokalizacja: Gumiland
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Wzór na ilość krawędzi oraz automorfizm.
Pierwsze zadanie akurat robiłem dziś na korepetycjach:
Oznaczmy wierzchołki grafu \(\displaystyle{ G}\) przez \(\displaystyle{ v_1,v_2, \dots , v_n}\). Weźmy dowolny wierzchołek \(\displaystyle{ v_i}\) i zauważmy, że jest on końcem \(\displaystyle{ deg(v_i)}\) krawędzi grafu \(\displaystyle{ G}\). Każda z tych krawędzi staje się wierzchołkiem w grafie krawędziowym \(\displaystyle{ L(G)}\), a co więcej każde takie dwa wierzchołki w \(\displaystyle{ L(G)}\) są połączone krawędzią generowaną przez \(\displaystyle{ v_i}\). Zatem ów wierzchołek generuje \(\displaystyle{ { deg(v_i) \choose 2}}\) krawędzi. W sumie więc w grafie krawędziowym \(\displaystyle{ L(G)}\) mamy:
\(\displaystyle{ \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:
\(\displaystyle{ -m + \frac{1}{2} \sum_{i=1}^{n} deg(v_i)^2}\)
gdzie \(\displaystyle{ m}\) jest liczbą krawędzi grafu \(\displaystyle{ G}\).
Q.
Oznaczmy wierzchołki grafu \(\displaystyle{ G}\) przez \(\displaystyle{ v_1,v_2, \dots , v_n}\). Weźmy dowolny wierzchołek \(\displaystyle{ v_i}\) i zauważmy, że jest on końcem \(\displaystyle{ deg(v_i)}\) krawędzi grafu \(\displaystyle{ G}\). Każda z tych krawędzi staje się wierzchołkiem w grafie krawędziowym \(\displaystyle{ L(G)}\), a co więcej każde takie dwa wierzchołki w \(\displaystyle{ L(G)}\) są połączone krawędzią generowaną przez \(\displaystyle{ v_i}\). Zatem ów wierzchołek generuje \(\displaystyle{ { deg(v_i) \choose 2}}\) krawędzi. W sumie więc w grafie krawędziowym \(\displaystyle{ L(G)}\) mamy:
\(\displaystyle{ \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:
\(\displaystyle{ -m + \frac{1}{2} \sum_{i=1}^{n} deg(v_i)^2}\)
gdzie \(\displaystyle{ m}\) jest liczbą krawędzi grafu \(\displaystyle{ G}\).
Q.
-
- Użytkownik
- Posty: 562
- Rejestracja: 20 maja 2013, o 16:33
- Płeć: Mężczyzna
- Lokalizacja: Kielce
- Podziękował: 98 razy
Wzór na ilość krawędzi oraz automorfizm.
A co w sytuacji gdy mamy wierzchołek stopnia 1 wtedy otrzymamy symbol Newtona \(\displaystyle{ {1 \choose 2}}\) i w jaki sposób otrzymać tamten wzór z lematu o usciskach?
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Wzór na ilość krawędzi oraz automorfizm.
Wierzchołek stopnia \(\displaystyle{ 1}\) w grafie \(\displaystyle{ G}\) nie generuje żadnej krawędzi w grafie \(\displaystyle{ L(G)}\) i zgadza się to z tym, że \(\displaystyle{ \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.
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.
-
- Użytkownik
- Posty: 562
- Rejestracja: 20 maja 2013, o 16:33
- Płeć: Mężczyzna
- Lokalizacja: Kielce
- Podziękował: 98 razy
Wzór na ilość krawędzi oraz automorfizm.
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?