Tekst źródłowy strony Graf krawędziowy


[[Plik:Garaph and line graph color.png|thumb|Graf i jego graf krawędziowy. Kolory pokazują przejście krawędzi w wierzchołki]]

'''Graf krawędziowy''' ([[język angielski|ang.]] ''line graph'') [[Graf (matematyka)|grafu]] G – taki graf F=L(G), którego zbiorem wierzchołków jest zbiór krawędzi grafu G: V(F) = E(G), natomiast zbiorem krawędzi E(F) jest zbiór par elementów zbioru E(G), przy czym:

W [[Graf (matematyka)|grafach nieskierowanych]]:
: Wierzchołki {v1, v2}, {v3, v4} grafu F są połączone wtedy i tylko wtedy, gdy v1=v3 lub v1=v4 lub v2=v3 lub v2=v4.
W [[graf skierowany|grafach skierowanych]]:
: Od wierzchołka (v1, v2) do wierzchołka (v3, v4) grafu F prowadzi krawędź wtedy i tylko wtedy, gdy v2=v3.

Intuicyjnie można to rozumieć tak, że krawędzie grafu G traktujemy jako wierzchołki, tworząc graf F, a wierzchołki grafu F łączymy krawędziami wtedy, gdy „istnieje przejście” pomiędzy krawędziami grafu G odpowiadającym odpowiednim wierzchołkom grafu F.

Jeśli nie powiedziano inaczej, pojęcie grafu krawędziowego odnosi się tylko do [[Graf (matematyka)|grafów nieskierowanych]].

Interesującym zagadnieniem jest pytanie, czy dany graf jest grafem krawędziowym jakiegoś grafu, oraz czy każdy graf jest grafem krawędziowym jakiegoś grafu.

[[Lowell W. Beineke]] w [[1968]] r. pokazał, że graf jest grafem krawędziowym jakiegoś grafu wtedy i tylko wtedy, gdy nie zawiera żadnego z dziewięciu wymienionych grafów:
[[Plik:Ind subg not in line graph.png|thumb|center|200px|9 indukowanych podgrafów nie zawartych w żadnym grafie krawędziowym]]

* Graf krawędziowy [[graf spójny|grafu spójnego]] jest grafem spójnym.
* <math>\chi'(G) = \chi(L(G)),</math> [[indeks chromatyczny]] grafu jest równy [[Kolorowanie grafu|liczbie chromatycznej]] jego grafu krawędziowego<ref name="colouring">{{Cytuj książkę |nazwisko = Diestel |imię = Reinhard |tytuł = Graph Theory |url=http://diestel-graph-theory.com/index.html |miejsce = Nowy Jork |rok = 2000 |strony = 96| isbn= 0-387-95014-1}}</ref>.

== Przypisy ==
{{Przypisy}}

{{Teoria grafów}}

{{Kontrola autorytatywna}}

[[Kategoria:Grafy|krawędziowy]]