K-реберно-зв'язний граф: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
|||
Рядок 2:
В [[теорія графів|теорії графів]], граф '''''k''-реберно-зв'язний''', якщо він залишається [[зв'язний граф|зв'язним]] по видаленню менше ніж ''k'' ребер.
== Формальне визначення ==
Нехай ''G'' = (''E'',''V'') довільний граф.
Якщо ''G'' = (''E'' \ ''X'',''V'') є зв'язним для всіх ''X'' ⊆ ''E'' де |''X''| < ''k'', тоді ''G'' — ''k''-реберно-зв'язний.
== Властивості ==
* Мінімальний [[Степінь вершини (теорія графів)|степінь вершин]] ''k''-реберно-зв'язного графу не менший від ''k''.
* [[Критичний граф]] із хроматичним числом >''k'' є ''k''-реберно-связним.
==Зв'язок з найменшим степенем вершини==
| |||