Экстремальные части графа. Глава 5

Август 22, 2022

Главная
Математика
Экстремальные части графа. Глава 5

Содержание

2. 5.1. Основные понятия
3. Ряд классических задач теории графов сводится к отысканию частей графа, экстремальных относительно некоторого свойства. Речь может
4. Максимальность и наибольшесть Определение. Наибольшей (наименьшей) частью графа по некоторому свойству называется макси-мальная (минимальная) часть с
5. Полные подграфы (клики) Максимальный полный подграф (клика - clique) обыкновенного графа – такой подграф, все вершины
6. Пустые подграфы (ВУМ) Максимальный пустой подграф (независимое множество, внутренне устойчивое множество) – такой подграф, все вершины
7. Покрытия (доминирующие множества) Из доминирующего множества «видны» все вершины графа. Иначе оно называется вершинно – вершинным
8. Задача о пяти ферзях Задача о часовых Пять ферзей бьют все поля доски
9. Опоры Из опорного множества вершин «видны» все ребра графа, поэтому оно называется вершинно – реберным покрытием.
10. Паросочетания Паросочетанием (matching) называется произвольное подмножество попарно несмежных ребер графа. Паросочетание не зависит от ориентации. Можно
11. Взвешенные графы Многие прикладные задачи сводятся к проблеме нахождения экстремальных частей во взвешенных графах. Требуется найти
12. 5.2. Взаимосвязи между задачами нахождения экстремальных частей
13. Задачи о нахождении наибольших полных и пустых подграфов превращаются одна в другую, если от исследуемого графа
14. Паросочетания и пустые подграфы G G’
15. Опоры и пустые подграфы
16. Таким образом, задача о нахождении наибольшего пустого подграфа (независимого множества) сводится к нахождению наименьшей опоры (вершинно-реберного
17. 5.3. Задача о наименьшем покрытии
18. Задача состоит в нахождении наименьшего подмно-жества столбцов, покрывающих все строки, т. е. из столбцов скомпоновать единичный
19. Задача о наименьшем покрытии формулируется на матрице общего вида. Применительно к графам она может быть поставлена
20. Доминирующее множество Для решения задачи о нахождении доминирующего множества (вершинно – вершинного покрытия) в качестве матрицы
21. Опора Для решения задачи о нахождении опорного множества (вершинно – реберного покрытия) в качестве матрицы А
23. Скачать презентацию

Слайд 2

5.1. Основные понятия

Слайд 3

Ряд классических задач теории графов сводится к отысканию частей графа, экстремальных

относительно некоторого свойства. Речь может идти о подмно-жествах вершин или ребер и о частях, порожденными этими подмножествами.

Слайд 4

Максимальность и наибольшесть

Определение. Наибольшей (наименьшей) частью графа по некоторому свойству называется

макси-мальная (минимальная) часть с наибольшим (наи-меньшим) числом элементов графа, обладающая этим свойством.

Таким образом, максимальность и минимальность рассматривается по включению, «наибольшесть» и «наименьшесть» – по числу элементов

Слайд 5

Полные подграфы (клики)
Максимальный полный подграф (клика - clique) обыкновенного графа –

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

Максимальные:

Слайд 6

Пустые подграфы (ВУМ)
Максимальный пустой подграф (независимое множество, внутренне устойчивое множество) –

такой подграф, все вершины которого попарно несмежны и он не содержится ни в каком другом пустом подграфе.

Задача о расстановке 8 ферзей на шахматной доске так, чтобы они друг друга не били. Есть 92 варианта.

Слайд 7

Покрытия (доминирующие множества)

Из доминирующего множества «видны» все вершины графа. Иначе оно

называется вершинно – вершинным покрытием. Обычным образом определяются минимальные (по включению) и наименьшие (по количеству вершин) доминирующие множества.

Слайд 8

Задача о пяти ферзях
Задача о часовых

Пять ферзей бьют все
поля доски

Слайд 9

Опоры

Из опорного множества вершин «видны» все ребра графа, поэтому оно называется

вершинно – реберным покрытием.
Существуют минимальные и наименьшие опоры.

∀u∈E∃x∈P:I(x,u)

Слайд 10

Паросочетания
Паросочетанием (matching) называется произвольное подмножество попарно несмежных ребер графа.
Паросочетание не зависит

от ориентации. Можно искать максимальное (по включению) и наибольшее (по числу ребер) паросочетание.

Это – совершенное паросочетание, так как оно покрывает все вершины графа.

Слайд 11

Взвешенные графы
Многие прикладные задачи сводятся к проблеме нахождения экстремальных частей во

взвешенных графах. Требуется найти обычно отыскивается наибольшую (наименьшую) часть с наибольшим (наименьшим) весом.
Пример – нахождение наибольшего по весу паросочетания в двудольном графе (задача о назначениях).

Слайд 12

5.2. Взаимосвязи между задачами
нахождения экстремальных частей

Слайд 13

Задачи о нахождении наибольших полных и пустых подграфов превращаются одна в

другую, если от исследуемого графа перейти к его дополнению до полного графа.

Полные и пустые подграфы

Слайд 14

Паросочетания и пустые подграфы

G
G’

Слайд 15

Опоры и пустые подграфы

Слайд 16

Таким образом, задача о нахождении наибольшего пустого подграфа (независимого множества) сводится

к нахождению наименьшей опоры (вершинно-реберного покрытия)
и наоборот.

Слайд 17

5.3. Задача о наименьшем покрытии

Слайд 18

Задача состоит в нахождении наименьшего подмно-жества столбцов, покрывающих все строки, т.

е. из столбцов скомпоновать единичный столбец.

Слайд 19

Задача о наименьшем покрытии формулируется на матрице общего вида. Применительно к

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

Слайд 20

Доминирующее множество
Для решения задачи о нахождении доминирующего множества (вершинно – вершинного

покрытия) в качестве матрицы А берется транспонированная матрица смежности неориентированного или ориентированного графа с единицами по диагонали.

Слайд 21

Опора
Для решения задачи о нахождении опорного множества (вершинно – реберного покрытия)

в качестве матрицы А берется транспонированная матрица инциденций соответствующего графа. Строки соответствуют ребрам, столбцы – вершинам графа.

Экстремальные части графа. Глава 5

Содержание

5.1. Основные понятия

Ряд классических задач теории графов сводится к отысканию частей графа, экстремальных

Максимальность и наибольшесть Определение. Наибольшей (наименьшей) частью графа по некоторому свойству называется

Полные подграфы (клики)Максимальный полный подграф (клика - clique) обыкновенного графа –

Пустые подграфы (ВУМ)Максимальный пустой подграф (независимое множество, внутренне устойчивое множество) –

Покрытия (доминирующие множества) Из доминирующего множества «видны» все вершины графа. Иначе оно

Задача о пяти ферзяхЗадача о часовых Пять ферзей бьют всеполя доски

Опоры Из опорного множества вершин «видны» все ребра графа, поэтому оно называется

ПаросочетанияПаросочетанием (matching) называется произвольное подмножество попарно несмежных ребер графа.Паросочетание не зависит

Взвешенные графы Многие прикладные задачи сводятся к проблеме нахождения экстремальных частей во

5.2. Взаимосвязи между задачаминахождения экстремальных частей