Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек
ГРАФЫ
Ссылки по теме графы:
1. https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D1%84_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)
2.
Способы представления графа в информатике
Список рёбер
Матрица инцидентности
хордальным
Матрица смежности
Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.
Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.
Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.
ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В ШКОЛЬНОМ КУРСЕ МАТЕМАТИКИ.
Задачи о "правильном" раскрашивании карт
В математике теорема о четырёх красках утверждает, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке общей границей для них не считаются. Эта теорема была сформулирована Фрэнсисом Гутри (англ.) в 1852 году, однако доказать ее долгое время не удавалось. В течение этого времени было предпринято множество попыток как доказательства, так и опровержения, и эта задача носила название проблемы четырёх красок.
Логические задачи
Один из способов решения задач типа «Кто есть кто?» - метод графов.
Граф – это несколько точек, часть которых соединены друг с другом
отрезками или стрелками (в этом случае граф называется
ориентированным).
Например
Петя, Гена, Дима и Вова занимаются в детской спортивной школе в
разных секциях: гимнастической, баскетбольной, волейбольной и легкой
атлетики. Петя, Дима и волейболист учатся в одном классе. Петя и Гена на
тренировки ходят пешком вместе, а гимнаст ездит на автобусе. Легкоатлет не
знаком ни с баскетболистом, ни с волейболистом. Кто из мальчиков в какой
секции занимается?
Между 9 планетами Солнечной системы введено космическое сообщение.
Ракеты летают по следующим маршрутам: Земля–Меркурий, Плутон–Венера,
Земля–Плутон, Плутон–Меркурий, Меркурий–Венера, Уран–Нептун, Нептун–Сатурн,
Сатурн–Юпитер, Юпитер–Марс и Марс–Уран. Можно ли добраться с Земли до Марса?
Встретились три подруги: Белова, Краснова и Чернова. На одной из них было
надето черное платье, на другой – красное, а на третьей белое. Девочка в красном платье
говорит Черновой: « Нам надо поменяться платьями, а то цвет наших платьев не
соответствует нашим фамилиям». Кто из девочек в какое платье был одет?
Задачи о мостах
Проблема семи мостов Кёнигсберга или Задача о кёнигсбергских мостах (нем. Königsberger Brückenproblem) — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году немецким и русским математиком Леонардом Эйлером.
Решение задачи по Леонарду Эйлеру
На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Если ровно две вершины графа нечётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой из нечётных вершин и завершить его в другой нечетной вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Граф кёнигсбергских мостов имел четыре (синим) нечётные вершины (то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Графы по типу связи
Мультиграф
В теории графов мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных рёбер[en] (их также называют «параллельными»[1]), то есть рёбра, имеющие те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром (тем самым мультиграфы отличаются от гиперграфов, в которых каждое ребро может соединять любое число вершин, а не в точности две).
Существует два различных способа обозначения рёбер мультиграфа. Некоторые говорят, что, как и в случае графов без кратных рёбер, ребро определяется вершинами, которые оно соединяет, но каждое ребро может повторяться несколько раз. Другие определяют рёбра равноправными с вершинами элементами графа и они должны иметь собственную идентификацию.
взвешенным
мультиграфы
полным двудольным
сильно связным или ориентированно связным
k-дольным
двудольным
Двудо́льный граф или бигра́ф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.
полным
Полный граф — простой граф, в котором каждая пара различных вершин смежна. Полный граф с n вершинами имеет n(n-1)/2 рёбер и обозначается K_n. Является регулярным графом степени n-1.
Полный ориентированный граф - это ориентированный граф, в котором каждая пара различных вершин соединена парой дуг (с различными направлениями).
Графы с K_1 по K_4 являются планарными. Полные графы с большим количеством вершин не являются планарными, так как содержат подграф K_5 и, следовательно, не удовлетворяют критерию Понтрягина-Куратовского.
Неориентированный граф
деревом
связным
Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь.
Виды графов
псевдографы
эйлеровы графы
Изоморфные графы
Графы G и H являются изоморфными, если путем перестановки строк и столбцов матрицы смежности графа G удается получить матрицу смежности графа H. Однако перебор всех возможных перестановок характеризуется вычислительной сложностью O(N!) (при условии, что сравнение матриц смежности производится за время, не зависящее от N, что обычно несправедливо и дополнительно увеличивает приведенную оценку), что существенно ограничивает применение подобного подхода на практике. Существуют методы ограниченного перебора возможных пар предположительно-изоморфных вершин (аналог метода ветвей и границ), однако они незначительно улучшают приведенную выше асимптотику[2].
Смешанный граф
Ориентированный граф
(мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами.
