Thickness of a graph

Материал из WikiGrapp
Версия от 12:29, 4 августа 2011; Glk (обсуждение | вклад) (Новая страница: «'''Thickness of a graph''' --- толщина графа. The ''' thickness''' <math>T(G)</math> of a graph <math>G</math> is the minimum number of planar subgraph…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Thickness of a graph --- толщина графа.

The thickness [math]\displaystyle{ T(G) }[/math] of a graph [math]\displaystyle{ G }[/math] is the minimum number of planar subgraphs of [math]\displaystyle{ G }[/math] whose union is [math]\displaystyle{ G }[/math]. It is known that the thickness [math]\displaystyle{ T }[/math] of a simple graph with [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ |E| }[/math] edges satisfies the following:

[math]\displaystyle{ T \geq \left \lceil \frac{|E|}{3n - 6}\right \rceil. }[/math]

For a complete graph [math]\displaystyle{ K_{n} }[/math]

[math]\displaystyle{ T \geq \left \lceil \frac{n(n-1)}{6(n-2)} \right \rceil = \left \lfloor \frac{n(n-1) + (6n-14)}{6(n-2)}\right \rfloor = \lfloor \frac{1}{6}(n + 7)\rfloor. }[/math]