Macierz incydencji grafu liniowego

[PiotrWP]

Graf \(\displaystyle{ G'}\) jest grafem liniowym (krawędziowym) grafu \(\displaystyle{ G}\) tzn. \(\displaystyle{ G' = L(G)}\). Mając macierz incydencji grafu \(\displaystyle{ G'}\) jak najłatwiej wyznaczyć rozkład stopni wierzchołków grafu \(\displaystyle{ G}\) ?

[arek1357]

Grafem krawędziowym nazywamy graf, powstały z danego grafu prostego(bo o takim mówię),
gdzie wierzchołki krawędziowego to krawędzie wyjściowego, a krawędzie między tymi punktami dajemy wtedy gdy krawędzie wyjściowego mają wspólny wierzchołek...

I teraz mając daną macierz incydencji grafu krawędziowego, możemy np. sobie graf krawędziowy narysować i zauważyć:

1. że ilość wierzchołków w krawędziowym to liczba krawędzi w wyjściowym, niech będzie np:\(\displaystyle{ n}\)

2. Ilość krawędzi w krawędziowym jest równa.: \(\displaystyle{ l}\)

Zapiszmy tak:

\(\displaystyle{ x}\)- ilość wierzchołków w wyjściowym takich, że: \(\displaystyle{ deg(v_{i}) \le 1}\)

\(\displaystyle{ k}\) - ilość wierzchołków w wyjściowym takich, że: \(\displaystyle{ deg(v_{i}) > 1}\)

\(\displaystyle{ 1< deg(v_{i})=y_{i}, i=1,...,k}\)

wiadomo, że ( ze znanego twierdzenia o stopniach wierzchołków i ilości krawędzi):

\(\displaystyle{ x' \le x}\)

\(\displaystyle{ x'+ \sum_{i=1}^{k}y_{i}=2n}\)

Następną równością z obserwacji jest:

\(\displaystyle{ {y_{1} \choose 2}+{y_{2} \choose 2}+...+ {y_{k} \choose 2}=l}\)

To co zaobserwowałem w grafach krawędziowych...