Line graph

Материал из WikiGrapp
Версия от 14:00, 31 мая 2011; 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…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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.