Wzór na ilość krawędzi oraz automorfizm.

[desertangel]

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.

[Qń]

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.

[Matiks21]

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?

[Qń]

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.

[Matiks21]

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?

[bakala12]

Tak. Dlaczego niby nie miałoby to być możliwe?