Phenquestions
Узел в графе называется вершиной (множественное число - вершины). Иногда его еще называют узлом; его также можно назвать точкой. Связь в графе называется ребром. Иногда это еще называют ссылкой; его также можно назвать линией.
График с множеством функций
На этом рисунке показан график с множеством функций:
Кружки (диски) - вершины. Любая прямая или изогнутая линия или петля является кромкой.
Особенности графика
Вершина
Вершина - это объект. Это может быть дом; это может быть человек; это может быть абстрактное существительное; это может быть любой объект, о котором вы только можете подумать.
Край
Ребро - это связь (отношение) между двумя вершинами; связь может быть абстрактной.
Петля
Петля - это ребро, соединяющее вершину с самим собой.
Край стрелки
Рассмотрим двух людей: Иоанна и Петра. Если Джон ссужает Питеру 100 долларов, и если Джон и Питер вершины, то кредитное ребро будет указывать на Питера. Если оба партнера забудут, что Питер должен Джону, а Питер одолжит Джону 100 долларов, то на другом конце того же края стрелка будет указывать на Джона. Если бы Питер одолжил Джону только 75 долларов, а не 100, тогда другое преимущество соединило бы Питера с Иоанном. У этого второго края будет стрелка, указывающая на Джона. Во втором случае есть два ребра с одной стрелкой на каждом, указывающие в противоположных направлениях.
Вершина, на которую указывает ребро, является головной вершиной этого ребра. Вершина, из которой выходит ребро, является вершиной хвоста.
Инцидент
Ребро соединяет две вершины. Ребро инцидентно любой вершине. На кромке не обязательно должна быть стрелка. Две вершины называются концами ребра. Возможен граф, вершина которого не принадлежит ни одному ребру, но это не будет рассматриваться в этом руководстве.
Ненаправленный граф
Ребро может быть стрелкой или не может. Граф, в котором нет края стрелки, является неориентированным графом. Кромка может быть представлена прямой линией, кривой или петлей.
Направленный график
Граф, в котором каждое ребро представляет собой стрелку (направление), является ориентированным графом. Край стрелки может быть представлен прямой линией со стрелкой, кривой со стрелкой или петлей с острием стрелки.
Отсутствие направления на краю неориентированного графа означает, что каждое ребро неориентированного графа является двунаправленным.
Степень вершины
Количество ребер, инцидентных вершине, - это степень вершины. У цикла есть два инцидента на вершине, поэтому цикл учитывается дважды.
Порядок графика
Порядок графа - это количество вершин в графе.
Мультиграф
Мультиграф - это граф, в котором для некоторых пар вершин имеется более одного ребра. Неориентированный мультиграф - это такой граф, в котором ребра не имеют направлений (не являются стрелками). Направленный мультиграф - это такой, в котором каждое ребро представляет собой стрелку, а для пар вершин, имеющих более одной стрелки, одна вершина является хвостом этих стрелок, а другая вершина - головкой тех же стрелок. На следующей диаграмме показан неориентированный мультиграф:
Более одного ребра (i.е. кратные ребра) для пары вершин также называются параллельными ребрами.
Колчан
Колчан - это мультиграф, в котором разрешены петли (одна или несколько петель). Некоторые мультиграфы не допускают петель.
Простой график
Простой граф - это граф, в котором никакие две пары вершин не имеют кратных ребер. Циклы не допускаются в простом графике.
Пустой график
Пустой граф - это граф без вершин и, следовательно, без ребер.
Смешанный график
Смешанный граф - это граф, в котором одни ребра являются стрелками, а другие - нет; другими словами: одни ребра имеют направление, а другие - нет.
Взвешенный график
Возможен график, в котором каждому ребру присваивается номер, известный как вес. Некоторые ребра имеют одинаковые номера, но, как правило, номера разные. Такой граф называется взвешенным графом. Числа для конкретного графика могут обозначать длину или стоимость (цены) или величину какого-либо вида, в зависимости от проблемы.
Степень и степень
Словарь, степень и исходящая степень применимы только к ориентированному графу. Граф может быть мультиграфом, а может и не быть. График может иметь или не иметь петель.
Количество наконечников стрелок, соединенных с вершиной, - это степень этой вершины. Стрела с одинарным наконечником имеет острие и острие. Количество хвостов, соединенных с вершиной, является исходной степенью этой вершины.
Примечание: граф с несколькими ребрами для пары вершин, где несколько ребер направлены в противоположные стороны, в этом руководстве не рассматривается.
Программное представление графа
Граф может быть представлен в программном обеспечении так, как он нарисован на диаграмме. Граф также может быть представлен в программном обеспечении математической матрицей (двумерным массивом). Одна из таких матриц называется матрицей смежности.
Матрица смежности
Матрица смежности - это квадратная матрица. Заголовки строк - это все вершины, записанные в порядке возрастания. Заголовки столбцов - все те же вершины, записанные в порядке возрастания. Подсчет строк или столбцов матрицы начинается с 1, а не с нуля, как в массивах. При идентификации элемента в матрице номер строки записывается первым перед номером столбца.
Для неориентированного графа каждая запись (элемент) в матрице смежности - это количество ребер, соединяющих две соответствующие вершины. Петлю нужно пересчитать дважды. Для ориентированного графа каждая запись в матрице смежности - это либо количество ребер, выходящих из вершины строки и входящих в соответствующую вершину столбца, либо количество ребер, выходящих из вершины столбца и входящих в соответствующую вершину строки. Выбор за программистом. В этой ситуации (в любом случае) цикл все равно следует считать один раз.
Примечание. График - это диаграмма, представляющая собой самостоятельную структуру данных. Матрица смежности также является самостоятельной структурой данных.
Ненаправленный граф и матрица смежности
На следующих диаграммах показан неориентированный граф и соответствующая матрица смежности:
Ведущая диагональ матрицы - это диагональ от верхнего левого угла до нижнего правого угла. Ненаправленная матрица симметрична относительно ведущей диагонали. Элемент матрицы для строки A и столбца C равен 1, что означает, что есть одно ребро, соединяющее вершину A и вершину C. Элемент матрицы для строки C и столбца B равен 3, что означает, что есть 3 ребра, соединяющие вершину C и вершину B. Остальные записи объясняются аналогичным образом.
Сумма записей в строке дает количество ребер (степень) для соответствующей вершины. Сумма записей для строки A равна 2, что означает, что 2 ребра соединены с вершиной A. Сумма записей для строки B равна 6, что означает, что 6 ребер соединены с вершиной B. Остальные записи объясняются аналогичным образом.
Направленный граф и матрица смежности
На следующих диаграммах показан ориентированный граф и соответствующая матрица смежности:
Матрица смежности для ориентированного графа не обязательно симметрична относительно главной диагонали. Матричный элемент для строки A и столбца C равен 1, что означает, что одно ребро уходит из вершины A в вершину C. Элемент матрицы для строки C и столбца B равен 3, что означает, что 3 ребра отходят от вершины C к вершине B. Остальные записи объясняются аналогичным образом.
Сумма записей для столбца дает степень вершины (столбца). Сумма записей для строки дает исходящую степень для (строки) вершины. Сумма записей в столбце A равна 1, что означает, что одно ребро направлено в вершину A. Сумма записей в строке B равна 2, что означает, что из вершины B отходят 2 ребра. Остальные записи объясняются аналогичным образом.
Графические операции
Структура данных, такая как график, состоит из набора значений данных или набора объектов, плюс отношения между объектами, плюс операции (функции) между объектами. Отношения в графе обозначены ребрами. При этом граф должен иметь как минимум следующие операции:
смежные (G, x, y)
G означает график. Эта операция проверяет, соединяет ли ребро вершину x и вершину y. Значение и позиция записи в матрице указывают соединение ребра (и его тип).
соседи (G, x)
Эта операция возвращает список всех вершин, которые напрямую связаны с вершиной x. Значение и позиция записи в матрице указывают на соединение ребра.
remove_vertex (G, x)
Эта операция удаляет вершину x из графа. Если у вершины не было ребра, проблем нет. Однако, если в вершине были связи, то связи (ребра) также следует удалить. Значение и позиция записи в матрице указывают на наличие определенной вершины. Если вершина удаляется, матрицу необходимо перенастроить.
add_vertex (G, x)
Это добавляет вершину x без добавления ребер или заменяет вершину, которая имела ребра, но была удалена. Значение и позиция записи в матрице указывают на наличие определенной вершины. Если добавляется вершина, матрицу необходимо перенастроить.
add_edge (G, x, y)
Эта операция добавляет новое ребро между вершиной x и вершиной y, если ребра там не было. Значение и позиция записи в матрице указывают на наличие определенного края. Если добавляется край, матрицу необходимо перенастроить.
remove_edge (G, x, y)
Эта операция удаляла бы ребро между вершиной x и вершиной y, если бы ребро было там. Значение и позиция записи в матрице указывают на наличие определенного края. Если кромка удалена, матрицу необходимо перенастроить.
get_vertex_value (G, x)
Эта операция возвращает значение v, связанное с вершиной x. Для этого вам понадобится мощный набор подмножеств для меток вершин и их значений.
set_vertex_value (G, x, v)
Эта операция дает новое значение v для значения, связанного с вершиной, x. Для этого вам понадобится мощный набор подмножеств для меток вершин и их значений.
Некоторые графы также связывают значения со своими ребрами. Такие графы нуждаются в следующих дополнительных операциях:
get_edge_value (G, x, y)
Эта операция возвращает значение v, связанное с ребром (x, y). Для этого вам понадобится набор степеней подмножеств для ребер и их значений.
set_edge_value (G, x, y, v)
Эта операция дает новое значение v для значения, связанного с ребром, (x, y). Для этого вам понадобится набор степеней подмножеств для ребер и их значений.
Заключение
Граф - это набор вершин, соединенных ребрами. Граф может быть неориентированным или направленным. Края могут быть ненаправленными или направленными. Петли могут присутствовать или отсутствовать на графике. Далее вам следует изучить набор, набор мощности и мультимножество, относящиеся к графам. После этого вы должны изучить различные типы графов, такие как ориентированный граф, регулярный граф, полный граф, двудольный граф, турнирный граф, потоковый сетевой граф и т. Д.
Chrys
Об авторе
Chrysanthus Forcha
Первооткрыватель математики Интеграция из первых принципов и родственных серий. Степень магистра технического образования со специализацией в области электроники и компьютерного программного обеспечения. Бакалавр электроники. У меня также есть знания и опыт на уровне магистра в области вычислительной техники и телекоммуникаций. Из 20 000 писателей я был 37-м лучшим писателем в devarticles.ком. Я работаю в этих сферах более 10 лет.
Просмотреть все сообщения
