Chromatic index: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''Chromatic index''' --- хроматический индекс, хроматический класс. This is the least integer <math>k</math> for which the edg…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Chromatic index''' --- хроматический индекс, хроматический класс.
'''Chromatic index''' — [[хроматический индекс]], [[хроматический класс]].


This is the least integer <math>k</math> for which the edges of <math>G</math> can be colored so
This is the least integer <math>k</math> for which the [[edge|edges]] of <math>G</math> can be colored so that [[adjacent edges|''adjacent'' edges]] have different colores. We denote it by
that ''adjacent'' edges have different colores. We denote it by
<math>q(G)</math>. Clearly, <math>q(G) = \chi(L(G))</math>. Here <math>L(G)</math> is the ''[[line graph]]'' of <math>G</math>.
<math>q(G)</math>. Clearly, <math>q(G) = \chi(L(G))</math>. Here <math>L(G)</math> is the ''line graph'' of <math>G</math>.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 12:35, 18 апреля 2013

Chromatic indexхроматический индекс, хроматический класс.

This is the least integer [math]\displaystyle{ k }[/math] for which the edges of [math]\displaystyle{ G }[/math] can be colored so that adjacent edges have different colores. We denote it by [math]\displaystyle{ q(G) }[/math]. Clearly, [math]\displaystyle{ q(G) = \chi(L(G)) }[/math]. Here [math]\displaystyle{ L(G) }[/math] is the line graph of [math]\displaystyle{ G }[/math].

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.