Вершина графа

Вершина графа [graph node] — элемент (точка) графа, обозначающий объект любой природы, входящий в множество объектов, описываемое графом. То же: узел, точка.

Изолированная вершина — та, которая не является концевой точкой какого-либо ребра. Степень вершины — число ребер, для которых она является концом (инцидентных к ней). Вершина называется нечетной, если ее степень — нечетное число, и четной, если ее степень — четное число; степень изолированной вершины — нулевая.

Для любого графа сумма степеней вершин равна удвоенному числу ребер. В конечном графе число нечетных вершин четно.

Смотреть что такое «Вершина графа» в других словарях:

вершина графа — Элемент (точка) графа, обозначающий объект любой природы, входящий в множество объектов, описываемое графом. То же: узел, точка. Изолированная вершина та, которая не является концевой точкой какого либо ребра. Степень вершины число ребер, для… … Справочник технического переводчика

Вершина — В Викисловаре есть статья «вершина» Вершина верхняя точка чего либо. Термин вершина может также означать: В топографии … Википедия

Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

ГРАФА ОБХОД — маршрут, содержащий все вершины или ребра графа и обладающий определенными свойствами. Наиболее известными Г. о. являются эйлеровы и гамильтоновы цепи и циклы. Маршрут (замкнутый маршрут) наз. эйлеровой … Математическая энциклопедия

Медиана графа — Связать? Медиана вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимальная возможная. Пусть необходимо выбрать место для размещения телефонного коммутатора, электроподстанции, баз снабжения в сети дорог или… … Википедия

Узел графа — [graph node] см. Вершина графа … Экономико-математический словарь

Остовы графа — Содержание 1 Остов графа 2 Теорема 3 Доказательство теоремы … Википедия

Разбиение графа — Пример разбиения параллельной граф схемы алгоритма логического управления. В составе блоков, отмеченных разными цветами, нет параллельных вершин Разбиение графа на подграфы (англ. Graph partition) (иногда в литературе также употребляется… … Википедия

Компонента сильной связности графа — Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связаны. Две пары вершин s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Сильно связными… … Википедия

Ребро графа — [graph verge] термин теории графов, линия, соединяющая пару смежных вершин графа. Ориентированное ребро, т.е. такое, для которого одна вершина считается началом, другая концом, называется дугой. (Следовательно, ребро можно рассматривать как… … Экономико-математический словарь

Источник

Основные определения теории графов

Содержание

Ориентированные графы [ править ]

Инцидентность (англ. incidence) — понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины [math]u,

Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).

Источник

Основные сведения из теории графов.

Вершины в графе могут отличаться друг от друга тем, скольким ребрам они принадлежат.

Степенью вершины называется число ребер графа, которым принадлежит эта вершина.

Обозначать степени вершин Л, В, С будем соответственно так: степ. А у степ. В, степ. С и т. п.

У графа на рисунке степ. А = 1; степ. В = 2.

Теорема. В графе Г сумма степеней всех его вершин —число четное, равное удвоенному числу ребер графа.

Теорема. Число нечетных вершин любого графа четно.

Пример. В графе Г вершины Л и В — связные, а вершины А и Н — несвязные.

Граф называется связным, если каждые две вершины его связные. Граф называется несвязным, если хотя бы две вершины его несвязные. Граф на рисунке связный:Граф на рисунке связным не является:Один и тот же граф может выглядеть на рисунках по-разному. Например, на трех рисунках мало похожих друг на друга, изображен один и тот же граф (полный граф с четырьмя вершинами).Чтобы убедиться в том, что два рисунка изображают один и гот же граф, необходимо проверить:

1. Одинаковое ли число вершин на обоих рисунках?

2. Одинаковое ли на них число ребер?

3. Одинаковое ли на них число вершин имеет степень k?

Сформулируем необходимое и достаточное условие соответствия двух рисунков одному и тому же графу. Они изображают один и тот же граф тогда и только тогда, когда между вершинами на первом и на втором рисунках существует такое взаимно однозначное соответствие, при котором:

1) две вершины графа на первом рисунке соединены ребром, если соединена ребром соответствующая пара вершин графа на втором рисунке;

2) две вершины графа на втором рисунке соединены ребром, если соединена ребром соответствующая пара вершин графа на первом рисунке.

Деревом называется всякий связный граф, не имеющий циклов (см. рис.):

Вершина дерева, степень которой равна единице, называется висячей вершиной (на рисунке висячие вершины выделены закрашенными кружками).

Теорема. Дерево с в вершинами имеет в — 1 ребро.

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

На рисунке изображен граф Г: некоторые ребра его пересекаются.

На рисунке этот же граф Г изображен так, что его ребра не пересекаются.Граф Г называют плоским, если его можно нарисовать на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины.

Рисунок графа, в котором никакие два его ребра не пересекаются, если не считать точками пересечения общие вершины, называют плоским представлением графа. Ясно, что плоское представление имеет только плоский граф. Обратно, у всякого плоского графа непременно найдется плоское представление. Плоские графы — простые циклы, деревья, лес, а также и граф, содержащий цикл, из вершин которого «выходят» деревья.

Примером не плоского графа может служить полный граф с пятью вершинами. Любые попытки нарисовать его плоское представление обречены на неудачу.

Сформулируем теорему о плоских графах

Теорема (Понтрягина — Куратовского). Граф является плоским тогда и только тогда, когда он не имеет подграфом графа типа I или типа II.

Граф, все ребра которого ориентированы, называется ориентированным графом.

Ориентированный граф изображен на рисунке

Одна и та же вершина ориентированного графа может служит началом для одних ребер и концом для других. Соответственно различают две степени вершины: степень выхода и степень входа.

Степенью выхода вершины А ориентированного графа называется число выходящих из А ребер (обозначение: степ.вых.А).

Степенью входа вершины А ориентированного графа называется число входящих в А ребер (обозначение: степ.вх.А).

В графе на рисунке:

степ.вых.D = 3; степ.вх. D = 0;

степ.вых.С = 0; степ.вх.С = 3;

степ.выx.F = 0; степ.вх. F = 0.

В ориентированных графах в зависимости от сочетания степеней входа и выхода для данной вершины будем рассматривать три частных случая.

Изолированной вершиной называется вершина, у которой и степень входа и степень выхода равны 0.

Источником называется вершина, степень выхода которой положительна, а степень входа равна 0.

Стоком называется вершина, степень входа которой положительна, а степень выхода равна 0.

На рисунке вершина F — изолированная, D — источник, С — сток.

Источник

Вершина (теория графов)

С точки зрения теории графов, вершины рассматриваются как лишённые характерных черт неделимые объекты, хотя они могут представлять некоторые структуры, зависящие от задачи, из которой возник граф. Например семантическая сеть — это граф, в котором вершины представляют понятие класса объектов.

Две вершины, образующие ребро, называются конечными вершинами ребра и говорят, что ребро инцидентно вершинам.

Говорят, что вершина w смежна другой вершине v, если граф содержит ребро (v, w). Окрестностью вершины v называется порождённый подграф, образованный всеми вершинами, смежными v.

Связанные понятия

Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице).

Упоминания в литературе

Связанные понятия (продолжение)

В теории графов графом-циклом называется граф, состоящий из единственного цикла, или, другими словами, некоторого числа вершин, соединённых замкнутой цепью. Граф-цикл с n вершинами обозначают как Cn. Число вершин в Cn равно числу рёбер и каждая вершина имеет степень 2, то есть любая вершина инцидентна ровно двум рёбрам.

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

В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.

В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества.

В теории графов графом пересечений называется граф, представляющий схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств.

В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.

Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связны. Две вершины s и t любого графа сильно связны, если существует ориентированный путь из s в t и ориентированный путь из t в s.

В теории графов неориентированный граф H называется минором графа G, если H может быть образован из G удалением рёбер и вершин и стягиванием рёбер.

В теории графов мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных рёбер (их также называют «параллельными»), то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром (тем самым мультиграфы отличаются от гиперграфов, в которых каждое ребро может соединять любое число вершин, а не в точности две).

Граф решётки — это граф, рисунок которого, вложенный в некоторое евклидово пространство Rn, образует регулярную мозаику. Это подразумевает, что группа биективных преобразований, переводящая граф в себя, является решёткой в теоретико-групповом смысле.

В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины (5 и более рёбер).

В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом.

Источник

Виды вершин и рёбер графа. Маршруты, цепи, циклы в графах

Виды вершин и рёбер графа

Пример 1. Найти звенья в графе, представленном на рис А (под примером).

Ответ. Звенья данного графа изображены линиями 8 и 11 без указания направления.

Иначе говорят также, что в описанном случае порядок двух концов ребра графа не существенен. В случае, когда порядок, в котором указаны вершины в инциденции, существенен, соответствующее ребро называет дугой.

Пример 2. Найти дуги в графе, представленном на рис А.

Пример 3. Найти петли в графе, представленном на всё том же рис А.

Голой называют вершину, которая не инцидентна ни одному ребру графа.

Пример 4. Найти голую вершину в графе, представленном на всё том же рис А.

Изолированной называется вершина графа, которая инцидентна одной или нескольким петлям.

Две вершины a и b называются смежными, если существует по крайней мере одно соединяющее их ребро. В частности, вершина смежна сама с собой в том и только в том случае, когда при ней имеется хотя бы одна петля.

Пример 5. В графе, представленном на рис А, найти изолированные вершины, смежные и не смежные вершины, вершины, смежные сами с собой.

Кратными называются рёбра, соединяющие одну и ту же пару вершин.

Пример 6. Найти кратные рёбра в графе, представленном на всё том же рис А.

Количество рёбер, инцидентных вершине графа, называется степенью этой вершины графа.

Маршруты, цепи и циклы в графах

Маршрут, в котором все рёбра различны, называется цепью.

Цепь, в которой все вершины, кроме, возможно, первой и последней, различны, называется простой цепью.

Замкнутая цепь с положительной длиной называется циклом. Замкнутая простая цепь с положительной длиной называется простым циклом.

Пример 7. В графе, представленном на рисунке ниже, найти примеры маршрута (указать длину), любой цепи, простой цепи, цепи, не являющейся простой, любого цикла (указать длину), простого цикла (указать длину).

Ответ. В данном графе:

Граф называется связным, если существует цепь между любыми двумя его вершинами.

Источник