K-связность — различия между версиями
Filchenko (обсуждение | вклад) (Небольшой комментарий) |
Filchenko (обсуждение | вклад) (форматирование) |
||
| Строка 1: | Строка 1: | ||
Связность - одна из топологических характеристик графа | Связность - одна из топологических характеристик графа | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Граф называется k-связным, если < | + | Граф называется <tex>k</tex>-связным, если <tex>\kappa(G) \ge k</tex> |
}} | }} | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Граф называется k-реберно связным, если < | + | Граф называется <tex>k</tex>-реберно связным, если <tex>\lambda(G) \ge k</tex> |
}} | }} | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Множество S вершин, ребер или вершин и ребер разделяет u и v, если u и v принадлежат различным [[компонентам графа]] < | + | Множество <tex>S</tex> вершин, ребер или вершин и ребер разделяет <tex>u</tex> и <tex>v</tex>, если <tex>u</tex> и <tex>v</tex> принадлежат различным [[Отношение_связности,_компоненты_связности| компонентам графа]] <tex>G-S</tex> |
}} | }} | ||
| − | Многие утверждения для связных графов можно обобщить для случая k-связности, однако аналог тривиального утверждения часто оказывается содержательным. Простейший пример - [[Теорема Менгера]], утверждение которой для <math>k=1</math> тривиально. | + | Многие утверждения для связных графов можно обобщить для случая <tex>k</tex>-связности, однако аналог тривиального утверждения часто оказывается содержательным. Простейший пример - [[Теорема Менгера]], утверждение которой для <math>k=1</math> тривиально. |
Версия 23:25, 13 октября 2010
Связность - одна из топологических характеристик графа
| Определение: |
| Граф называется -связным, если |
| Определение: |
| Граф называется -реберно связным, если |
| Определение: |
| Множество вершин, ребер или вершин и ребер разделяет и , если и принадлежат различным компонентам графа |
Многие утверждения для связных графов можно обобщить для случая -связности, однако аналог тривиального утверждения часто оказывается содержательным. Простейший пример - Теорема Менгера, утверждение которой для тривиально.
