Связные компоненты графа. Разделяющие множества и разрезы

Август 1, 2022

Главная
Математика
Связные компоненты графа. Разделяющие множества и разрезы

Содержание

2. Связность Пусть G =(V, E) – н-граф. Связными называются вершины a и b если существуют маршрут,
3. Связность Утверждение: отношение связности является отношением эквивалентности. Доказательство: 1.Каждая вершина связана сама с собой маршрутом нулевой
4. Связность 2. Если вершина a связна с b, то и b связна с a. Если a
5. Связность 3. Если вершина a связана маршрутом с b, b связана с с, то и a
6. Связность Отношение рефлексивно, симметрично и транзитивно, значит является отношением эквивалентности. Множество вершин V разбивается отношением связности
7. Связность Связными компонентами графа G называются подграфы, порожденные классами эквивалентности по отношению связности. Замечание: В связном
8. Связны компоненты V={a,b,c,d,g}, класс V1={ a,c,d } класс V2={b,g}
9. Разделяющие множества Разделяющим множеством н-графа G =(V, E) называется множество ребер, при удалении которых число компонент
10. Разделяющие множества Разрезом в н-графе G =(V, E) называется разделяющее множество в котором нет лишних ребер,
11. Разделяющие множества Мостом или перешейком в н-графе G =(V, E) называется разрез, состоящий из одного ребра.
12. Разделяющие множества Разделяющее множество {(1,4), (2,3), (7,8)}; Разрез {(1,4), (2,3)}, (7,8) – лишнее; Мост {(4,5).
13. Шарнир Вершина - н-графа G =(V, E) называется шарниром, если удаление этой вершины и всех инцидентных
15. Скачать презентацию

Слайд 2

Связность
Пусть G =(V, E) – н-граф.
Связными называются вершины a и b

если существуют маршрут, связывающий их.
Н-граф G называется связным, если все его вершины связны

Слайд 3

Связность
Утверждение: отношение связности является отношением эквивалентности.
Доказательство:
1.Каждая вершина связана сама с собой

маршрутом нулевой длины, значит отношение связости рефлексивно.

Слайд 4

Связность
2. Если вершина a связна с b, то и b связна

с a. Если a с b связаны маршрутом М(a,b), то b с a связаны маршрутом М(b,a), где ребра и вершины идут в обратном порядке. Значит отношение связости симметрично.

Слайд 5

Связность
3. Если вершина a связана маршрутом с b, b связана с

с, то и a связана маршрутом с с. Это маршрут, начало которого М(a,b), окончание – M(b,c), вершина b – общая.
Значит отношение связости транзитивно.

Слайд 6

Связность
Отношение рефлексивно, симметрично и транзитивно, значит является отношением эквивалентности.
Множество вершин V

разбивается отношением связности на классы эквивалентности – подмножества связных вершин.

Слайд 7

Связность
Связными компонентами графа G называются подграфы, порожденные классами эквивалентности по отношению

связности.
Замечание: В связном графе одна связная компонента.

Слайд 8

Связны компоненты
V={a,b,c,d,g}, класс V1={ a,c,d }
класс V2={b,g}

Слайд 9

Разделяющие множества
Разделяющим множеством
н-графа G =(V, E) называется множество ребер, при

удалении которых число компонент связности графа увеличивается.

Слайд 10

Разделяющие множества
Разрезом в н-графе G =(V, E) называется разделяющее множество в

котором нет лишних ребер, то есть минимальное разделяющее множество.

Слайд 11

Разделяющие множества
Мостом или перешейком
в н-графе G =(V, E) называется

разрез, состоящий из одного ребра.

Слайд 12

Разделяющие множества
Разделяющее множество
{(1,4), (2,3), (7,8)};
Разрез {(1,4), (2,3)}, (7,8) – лишнее;
Мост

{(4,5).

Слайд 13

Шарнир
Вершина - н-графа G =(V, E) называется шарниром, если удаление этой

вершины и всех инцидентных ей ребер приводит к увеличению числа компонент связности графа.