Граф каркасов: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Граф каркасов''' (''Tree graph'') - граф <math>{\cal G}(G)</math>, вершины которого суть ''карк...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Граф каркасов''' (''Tree graph'') | '''Граф каркасов''' (''[[Tree graph]]'') — [[граф]] <math>\mathcal {G}(G)</math>, [[вершина|вершины]] которого суть [[каркас|''каркасы'']] графа <math>G</math> и две [[смежные вершины|вершины смежны]], если соответствующие каркасы имеют в точности <math>(n-2)</math> общих [[ребро|ребер]], где <math>n = |V(G)|</math>. '''Граф каркасов''' любого графа гамильтонов. | ||
граф <math>{ | |||
<math>G</math> и две вершины смежны, если соответствующие каркасы имеют в | |||
точности <math>(n-2)</math> общих ребер, где <math>n = |V(G)|</math>. ''' | |||
графа гамильтонов. | |||
==Литература== | ==Литература== | ||
* Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978. | |||
Текущая версия от 15:37, 1 февраля 2011
Граф каркасов (Tree graph) — граф [math]\displaystyle{ \mathcal {G}(G) }[/math], вершины которого суть каркасы графа [math]\displaystyle{ G }[/math] и две вершины смежны, если соответствующие каркасы имеют в точности [math]\displaystyle{ (n-2) }[/math] общих ребер, где [math]\displaystyle{ n = |V(G)| }[/math]. Граф каркасов любого графа гамильтонов.
Литература
- Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.