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

Категория: Математика
Нажмите для полного просмотра!
Связные компоненты графа. Разделяющие множества и разрезы, слайд №1Связные компоненты графа. Разделяющие множества и разрезы, слайд №2Связные компоненты графа. Разделяющие множества и разрезы, слайд №3Связные компоненты графа. Разделяющие множества и разрезы, слайд №4Связные компоненты графа. Разделяющие множества и разрезы, слайд №5Связные компоненты графа. Разделяющие множества и разрезы, слайд №6Связные компоненты графа. Разделяющие множества и разрезы, слайд №7Связные компоненты графа. Разделяющие множества и разрезы, слайд №8Связные компоненты графа. Разделяющие множества и разрезы, слайд №9Связные компоненты графа. Разделяющие множества и разрезы, слайд №10Связные компоненты графа. Разделяющие множества и разрезы, слайд №11Связные компоненты графа. Разделяющие множества и разрезы, слайд №12Связные компоненты графа. Разделяющие множества и разрезы, слайд №13Связные компоненты графа. Разделяющие множества и разрезы, слайд №14
Скачать
Вы можете ознакомиться и скачать презентацию на тему Связные компоненты графа. Разделяющие множества и разрезы. Доклад-сообщение содержит 14 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


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

Слайд 2


Связность Пусть G =(V, E) – н-граф. Связными называются вершины a и b если существуют маршрут, связывающий их. Н-граф G называется связным, если все его вершины связны
Описание слайда:
Связность Пусть G =(V, E) – н-граф. Связными называются вершины a и b если существуют маршрут, связывающий их. Н-граф G называется связным, если все его вершины связны

Слайд 3


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

Слайд 4


Связность 2. Если вершина a связна с b, то и b связна с a. Если a с b связаны маршрутом М(a,b), то b с a связаны маршрутом М(b,a), где ребра и вершины идут в обратном порядке. Значит отношение связости симметрично.
Описание слайда:
Связность 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 – общая. Значит отношение связости транзитивно.
Описание слайда:
Связность 3. Если вершина a связана маршрутом с b, b связана с с, то и a связана маршрутом с с. Это маршрут, начало которого М(a,b), окончание – M(b,c), вершина b – общая. Значит отношение связости транзитивно.

Слайд 6


Связность Отношение рефлексивно, симметрично и транзитивно, значит является отношением эквивалентности. Множество вершин V разбивается отношением связности на классы эквивалентности – подмножества связных вершин.
Описание слайда:
Связность Отношение рефлексивно, симметрично и транзитивно, значит является отношением эквивалентности. Множество вершин V разбивается отношением связности на классы эквивалентности – подмножества связных вершин.

Слайд 7


Связность Связными компонентами графа G называются подграфы, порожденные классами эквивалентности по отношению связности. Замечание: В связном графе одна связная компонента.
Описание слайда:
Связность Связными компонентами графа G называются подграфы, порожденные классами эквивалентности по отношению связности. Замечание: В связном графе одна связная компонента.

Слайд 8


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

Слайд 9


Разделяющие множества Разделяющим множеством н-графа G =(V, E) называется множество ребер, при удалении которых число компонент связности графа увеличивается.
Описание слайда:
Разделяющие множества Разделяющим множеством н-графа G =(V, E) называется множество ребер, при удалении которых число компонент связности графа увеличивается.

Слайд 10


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

Слайд 11


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

Слайд 12


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

Слайд 13


Шарнир Вершина - н-графа G =(V, E) называется шарниром, если удаление этой вершины и всех инцидентных ей ребер приводит к увеличению числа компонент связности графа.
Описание слайда:
Шарнир Вершина - н-графа G =(V, E) называется шарниром, если удаление этой вершины и всех инцидентных ей ребер приводит к увеличению числа компонент связности графа.

Слайд 14


Шарнир Шарниром является вершина 4.
Описание слайда:
Шарнир Шарниром является вершина 4.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию