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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Связные компоненты графа. Разделяющие множества и разрезы. Доклад-сообщение содержит 14 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 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) называется шарниром, если удаление этой вершины и всех инцидентных ей ребер приводит к увеличению числа компонент связности графа.