Раскраска графов - презентация, доклад, проект скачать

Содержание ▲

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

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

Слайд 1

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

Раскраска графов Иванов Алексей, МП-41

Слайд 2

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

Немного истории Первой работой теории графов как математической дисциплины считают статью Эйлера (1736г.), в которой рассматривалась задача о Кёнигсбергских мостах.

Слайд 3

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

Что такое граф? Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами).

Слайд 4

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

Слайд 5

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

Определение Раскраской вершин графа называется назначение цветов его вершинам. Обычно цвета - это числа 1,2…k . Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения в множестве {1,2…k}. Раскраску можно также рассматривать как разбиение множества вершин V = V1 u V2 u…u Vk, где Vi - множество вершин цвета i .

Слайд 6

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

Вид правильной раскраски графа

Слайд 7

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

Алгоритм неявного перебора

Слайд 8

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

Приближенный алгоритм (эвристический метод)

Слайд 9

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

Раскраска ребер графа Минимальное число цветов, необходимое для правильной раскраски ребер графа G, называется хроматическим индексом графа и обозначается через χ’(G) .