Графы. Описание графов. Задача Прима-Краскала - презентация, доклад, проект скачать

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

Графы. Описание графов. Задача Прима-Краскала, слайд №1

Графы. Описание графов. Задача Прима-Краскала, слайд №2

Графы. Описание графов. Задача Прима-Краскала, слайд №3

Графы. Описание графов. Задача Прима-Краскала, слайд №4

Графы. Описание графов. Задача Прима-Краскала, слайд №5

Графы. Описание графов. Задача Прима-Краскала, слайд №6

Графы. Описание графов. Задача Прима-Краскала, слайд №7

Графы. Описание графов. Задача Прима-Краскала, слайд №8

Графы. Описание графов. Задача Прима-Краскала, слайд №9

Графы. Описание графов. Задача Прима-Краскала, слайд №10

Графы. Описание графов. Задача Прима-Краскала, слайд №11

Графы. Описание графов. Задача Прима-Краскала, слайд №12

Графы. Описание графов. Задача Прима-Краскала, слайд №13

Содержание ▲

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

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

Слайд 1

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

Графы Лекция №9

Слайд 2

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

Графы

Слайд 3

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

Графы Если дуги имеют направление (вспомните улицы с односторонним движением), то такой граф называется направленным или ориентированным графом (орграфом). Цепью называется последовательность ребер, соединяющих две (возможно не соседние) вершины u и v. В направленном графе такая последовательность ребер называется «путь». Граф называется связным, если существует цепь между любой парой вершин. Если граф не связный, то его можно разбить на k связных компонент – он называется k-связным. В практических задачах часто рассматриваются взвешенные графы, в которых каждому ребру приписывается вес (или длина). Такой граф называют сетью. Циклом называется цепь из какой-нибудь вершины v в нее саму. Деревом называется граф без циклов. Полным называется граф, в котором проведены все возможные ребра (для графа, имеющего n вершин таких ребер будет n(n-1)/2).

Слайд 4

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

Описание графов Для описания графов часто используют два типа матриц – матрицу смежности (для невзвешенных графов) и весовую матрицу (для взвешенных). Часто вместо логических значений (истина/ложь) используют целые числа (1/0). Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали. Для ориентированных графов это не всегда так, потому что может существовать путь из вершины i в вершину j и не существовать обратного пути.

Слайд 5

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

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

Слайд 6

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

Задача Прима-Краскала Город будем изображать узлом (вершиной). Телефонные линии могут разветвляться только на телефонных станциях, а не в чистом поле. Поскольку требуется линия минимальной общей длины, в ней не будет циклов, потому что иначе можно было бы убрать одно звено цикла и станции по-прежнему были бы связаны. В терминах теории графов эта задача звучит так:

Слайд 7

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

Жадные алгоритмы Представим себе зимовщика, которому предоставили некоторый запас продуктов на всю зиму. Конечно, он может сначала съесть все самое вкусное – шоколад, мясо и т.п., но за такой подход придется жестоко расплачиваться в конце зимовки, когда останется только соль и маргарин. Подобным образом, если оптимальное решение строится по шагам, обычно нельзя выбирать на каждом этапе «самое вкусное» – за это придется расплачиваться на последних шагах. Такие алгоритмы называют жадными. Для решения задачи Прима-Краскала используется жадный алгоритм: Требуется проверить, чтобы циклов не было. Сделать это можно так: в самом начале покрасим все вершины в разные цвета и затем, выбрав очередное ребро между вершинами i и j, где i и j имеют разные цвета, перекрасим вершину j и все соединенные с ней (то есть имеющие ее цвет) в цвет i. Таким образом, при выборе ребер, соединяющих вершины разного цвета, цикл не возникнет никогда, а после n-1 шагов все вершины будут иметь один цвет.