143
правки
Изменения
Черновик конспекта
Связность - одна из топологических характеристик графа
{{Определение
|definition=
'''Числом вершинной связности''' <math>\kappa(G)</math> называется наименьшее число вершин, которое надо удалить, чтобы граф потерял связность.
}}
{{Определение
|definition=
'''Числом реберной связности''' <math>\lambda(G)</math> называется наименьшее число ребер, которое надо удалить, чтобы граф потерял связность.
}}
{{Определение
|definition=
Граф называется k-связным, если <math>\kappa(G) \ge k</math>
}}
{{Определение
|definition=
Граф называется k-реберно связным, если <math>\lambda(G) \ge k</math>
}}
<math>\kappa(G) \le \lambda(G) \le \delta(G)</math>, где <math>\lambda(G)</math> - минимальная степень вершины
{{Определение
|definition=
'''Числом вершинной связности''' <math>\kappa(G)</math> называется наименьшее число вершин, которое надо удалить, чтобы граф потерял связность.
}}
{{Определение
|definition=
'''Числом реберной связности''' <math>\lambda(G)</math> называется наименьшее число ребер, которое надо удалить, чтобы граф потерял связность.
}}
{{Определение
|definition=
Граф называется k-связным, если <math>\kappa(G) \ge k</math>
}}
{{Определение
|definition=
Граф называется k-реберно связным, если <math>\lambda(G) \ge k</math>
}}
<math>\kappa(G) \le \lambda(G) \le \delta(G)</math>, где <math>\lambda(G)</math> - минимальная степень вершины
