Рёберная раскраска двудольного графа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |id = edge_colouring |neat = 0 |definition = '''Рёберной раскрасксой''' (англ. ''Edge colouring'') <tex>\chi '(G)<...»)
 
Строка 1: Строка 1:
 +
 +
== Основные определения ==
 +
 +
 +
 
{{Определение
 
{{Определение
 
|id = edge_colouring
 
|id = edge_colouring
|neat = 0
+
|neat = 1
|definition = '''Рёберной раскрасксой''' (англ. ''Edge colouring'') <tex>\chi '(G)</tex> графа <tex>G(V, E)</tex> называется отображение <tex>\varphi:E \rightarrow \{c_{1}...c_{t}\}</tex> такое, что для для любых двух различных рёбер <tex>e_{i}, e_{j}</tex> инцидентных одной вершине верно, что <tex> \varphi (e_{i}) \neq \varphi (e_{j})</tex>  
+
|definition = '''Рёберной раскраской''' (англ. ''Edge colouring'') графа <tex>G(V, E)</tex> называется отображение <tex>\varphi:E \rightarrow \{c_{1}...c_{t}\}</tex> такое, что для для любых двух различных рёбер <tex>e_{i}, e_{j}</tex> инцидентных одной вершине верно, что <tex> \varphi (e_{i}) \neq \varphi (e_{j})</tex>.
 +
}}
 +
 
 +
 
 +
{{Определение
 +
|id = chromativ_index
 +
|neat = 1
 +
|definition = '''Хроматическим индексом''' (англ. ''Chromatic index'') <tex>\psi '(G)</tex> графа <tex>G(V, E)</tex> называется такое минимальное число '''t''', что существует рёберная раскраска графа в '''t''' цветов.
 
}}
 
}}

Версия 23:34, 18 ноября 2017

Основные определения

Определение:
Рёберной раскраской (англ. Edge colouring) графа [math]G(V, E)[/math] называется отображение [math]\varphi:E \rightarrow \{c_{1}...c_{t}\}[/math] такое, что для для любых двух различных рёбер [math]e_{i}, e_{j}[/math] инцидентных одной вершине верно, что [math] \varphi (e_{i}) \neq \varphi (e_{j})[/math].



Определение:
Хроматическим индексом (англ. Chromatic index) [math]\psi '(G)[/math] графа [math]G(V, E)[/math] называется такое минимальное число t, что существует рёберная раскраска графа в t цветов.