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