Содержание
- 2. Содержание: Графы: определения и примеры Путь в графе Решение логических задач Ориентированные графы Путь в орграфе
- 3. Графы: определения и примеры Говоря простым языком, граф - это множество точек (для удобства изображения -
- 4. Рис. 1. Три способа изображения одного графа Например, три графа на рис. 1 совпадают
- 5. А два графа на рис. 2 - различны Рис. 2. Пример двух разных графов
- 6. Д К М Б Р Граф – это графическое изображение состава и структуры системы. Граф состоит
- 7. Степень вершины (deg) Любому ребру соответствует ровно две вершины, а вот вершине может соответствовать произвольное количество
- 8. Теорема 1. В графе G(V,X) сумма степеней всех его вершин – число четное, равное удвоенному числу
- 9. Полный граф Граф G называется полным, если любые две его различные вершины соединены одним и только
- 10. Смежные вершины и рёбра Две вершины называются смежными, если они являются разными концами одного ребра. Два
- 11. Путь в графе Путь в графе - это последовательность вершин (без повторений), в которой любые две
- 12. Достижимость Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в
- 13. Длина пути Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже упомянутых
- 14. Примеры неориентированных графов
- 15. Метод графов – один из способов решения логических задач. По условию задачи составляется схема, состоящая из
- 16. Используя метод графов, решите задачу самостоятельно. Пять приятелей при встрече пожали друг другу руки. Сколько всего
- 17. Прием моделирования с помощью графов Ситуации, в которых требуется найти соответствие между элементами различных множеств, можно
- 18. Три товарища –Иван, Дмитрий и Степан преподают различные предметы (химию, биологию и физику) в школах Москвы
- 19. В задаче можно выделить три множества: учебных предметов, городов, учителей. Каждое множество содержит по три элемента.
- 20. По условию задачи будем соединять точки отрезками (сплошными линиями), если имеет место соответствие между данными элементами,
- 21. Москвич преподает физику.
- 22. Анализируя полученные связи, делаем вывод: житель Тулы преподает биологию. Тот, кто работает в Новгороде, преподает химию.
- 23. Дмитрий и Степан преподают не биологию. Добавляем два пунктирных ребра. Анализируя полученные связи, делаем вывод: биологию
- 24. Снова смотрим на граф и анализируем связи. Иван не живет в Москве, Иван преподает биологию. В
- 25. Анализируем рёбра графа. Иван живёт в Туле. Степан живёт в Новгороде. Следовательно, в Москве живёт Дмитрий.
- 26. Получаем ответ (двигаясь по вершинам графа, образующим сплошные треугольники): Иван живёт в Туле и преподает биологию.
- 27. Используя метод графов, решите задачу самостоятельно. Однажды на отдыхе за круглым столом оказались пятеро ребят родом
- 28. Ориентированные графы Орграф - это граф, все ребра которого имеют направление. Такие направленные ребра называются дугами.
- 29. Смешанный граф В отличие от ребер, дуги соединяют две неравноправные вершины: одна из них называется началом
- 30. Путь в орграфе Путь в орграфе - это последовательность вершин (без повторений), в которой любые две
- 31. Примеры ориентированных графов
- 32. Задание А)Нарисуйте граф системы «Компьютер», содержащий следующие вершины: процессор, оперативная память, внешняя память, клавиатура, дисплей, принтер.
- 33. Взвешенные графы Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам которого
- 34. Длина пути во взвешенном графе Длина пути во взвешенном (связном) графе - это сумма длин (весов)
- 35. Примеры взвешенных графов
- 36. Способы представления графов Существует довольно большое число разнообразных способов представления графов. Однако мы изложим здесь только
- 37. Способы представления графов Графически Граф, представленный на рис., состоит из множества вершин и множество дуг
- 38. Перечислением Множеством образов где - образ вершины множество вершин, в которые исходят дуги из данной вершины.
- 39. Способы представления графов Матрица инцидентности Матрица инцидентности - это матрица вершин и инцидентных им дуг. Дуга
- 40. Для графа, представленного на рис. матрица инцидентности имеет вид: Способы представления графов Матрица инцидентности для ориентированного
- 41. На практике в матрице инцидентности иногда нули не проставляются для наглядности. Свойство матрицы инцидентности – сумма
- 42. Пример: Построить матрицу инцидентности для графа, изображённого на рисунке Способы представления графов Матрица инцидентности
- 43. Способы представления графов Матрица инцидентности Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ)
- 44. Способы представления графов Матрица инцидентности для неориентированного графа Матрица инцидентности для неориентированного графа составляется по правилу:
- 45. Способы представления графов Матрица инцидентности для неориентированного графа Для графа, представленного на рис., матрица инцидентности имеет
- 46. Пример: Построить матрицу инцидентности для графа, изображённого на рисунке Способы представления графов Матрица инцидентности
- 47. Пример: Построить матрицу инцидентности для графа, изображённого на рисунке Способы представления графов Матрица инцидентности
- 48. Решение
- 49. Способы представления графов Матрица инцидентности Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ)
- 50. Матрица смежности Sm - это квадратная матрица размером N x N (N - количество вершин в
- 51. Пример матрицы смежности для взвешенного графа Рис. Взвешенный граф
- 52. Для неориентированного графа эта матрица определяется следующим образом. Если вершины и являются смежными, то . В
- 53. Способы представления графов Пример матрицы смежности для неориентированного графа
- 54. Преимущества матрицы смежности Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании.
- 55. Граф иерархической системы называется деревом. Иерархическими называются системы, между элементами которых установлены отношения подчинения или вхождения
- 56. Иерархическая структура университета (университет-факультеты-специальности-студент) университет Юридический факультет Исторический факультет Экономический факультет История Политология Финансы и кредит
- 57. Примерами иерархической системы в информатике является файловая система диска.
- 58. Гамильтоновы графы Граф называется гамильтоновым, если для каждой вершины графа найдется маршрут начинающейся и заканчивающей в
- 59. Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, а ребра — связывающие
- 60. К сожалению, эффективный алгоритм решения данной задачи пока не известен. Для сложных сетей число гамильтоновых циклов,
- 61. Для полных графов поиск гамильтоновых циклов осуществляться с помощью алгоритма ближайшего соседа: 1. Выбрать исходную вершину
- 63. Скачать презентацию