Line graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Line graph''' --- реберный граф. The '''line graph''' <math>L(G)</math> of a graph <math>G</math> is that whose vertices are the edges of <math>G</m…») |
(нет различий)
|
Текущая версия от 14:00, 31 мая 2011
Line graph --- реберный граф.
The line graph [math]\displaystyle{ L(G) }[/math] of a graph [math]\displaystyle{ G }[/math] is that whose vertices are the edges of [math]\displaystyle{ G }[/math] and two vertices of [math]\displaystyle{ L(G) }[/math] are adjacent iff the correspondent edges of [math]\displaystyle{ G }[/math] have an end vertex in common.
The [math]\displaystyle{ n }[/math]-iterated line graph [math]\displaystyle{ L^{n}(G) }[/math] of a graph [math]\displaystyle{ G }[/math] is defined to be [math]\displaystyle{ L(L^{n-1}(G)) }[/math], where [math]\displaystyle{ L^{1}(G) }[/math] denotes the line graph [math]\displaystyle{ L(G) }[/math] of [math]\displaystyle{ G }[/math], and [math]\displaystyle{ L^{n-1}(G) }[/math] is assumed to have a nonempty edge set.