Висячие вершины графа
Доброго времени. Подскажите, пожалуйста, тяжело разобраться с темой висячих вершин. Такое задание:
Дерево имеет 30 вершин, причём 4 вершины имеют степень 3, а остальные – не больше 2. Сколько в этом дереве висячих вершин?
Не пойму алгоритм, как нужно считать. Нужно ли включать в решение правило о сумме степеней вершин и ребрах?
Найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа
Пользуясь алгоритмом Дейкстры, найти кратчайшее расстояние из вершины v1 неориентированного.
Влияет ли петля на степень вершины графа?
Влияет ли петля на степень вершины графа?
Чему равна степень вершины 1 графа на рисунке?
Чему равна степень вершины 1 графа на рисунке?
Сообщение было отмечено ncuxuatop как решение
Решение
Сообщение от mathmichel
Сообщение было отмечено 3D Homer как решение
Решение
Сообщение от ncuxuatop
Вообще-то говоря такой довод, да и доводы уважаемого mathmichel ни в чем не убеждают.
Мне кажется вот такие доводы более убедительны:
1) пусть k — число вершин степени 2, m — число вершин степени 1 (или висячих, как вы их называете);
2) число ребер дерева с 30-ю вершинами равно 29;
3) тогда k+m+4=30 или k+m=26;
4) по теореме о рукопожатиях имеем 2k+m+12=2*29 или 2k+m=46;
5) вычитая из равенства 4 равенство 3, получим k=20, а вот тогда m=6.
Сообщение от kabenyuk
Сообщение от mathmichel
Сообщение от mathmichel
Как разбить вершины графа на слои, используя матрицу смежности?
Есть такой граф. Нужно разбить его вершины на слои используя графический способ и используя матрицу.
Дан неорграф, занумеровать вершины графа и определить степени всех его вершин
Дан неорграф G1 (рис. 3). Занумеруйте вершины графа и определите степени всех его вершин.
Нахождение фактора графа и остова графа для некоторого произвольного графа (5-6 вершин)
Форумчане прошу помощь в выполнение задания по деск. мат. Задание: Нахождение фактора графа и.
Описать граф, найти маршруты длинной 4 и 5 вершины А до вершины С. Найти циклы и их длинну с вершины Е
Описать граф, найти маршруты длинной 4 и 5 вершины А до вершины С. Найти циклы и их длинну с.
Удалить из графа изолированные и висячие вершины
Есть граф, у которого (abcdefg) — вершины, а ((bc) (bg) (cg) (cd) (ge)) — pебpа. Удалить из графа.
Удалить из графа изолированные и висячие вершины
Есть граф, у которого (abcdefg) — вершины, а ((bc) (bg) (cg) (cd) (ge)) — pебpа. Удалить из графа.
Что такое висячие вершины графа
Код баннера:
Исследовательские работы и проекты
Виды графов
1.2. Виды графов
Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)
Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3)
Графы, в которых построены все возможные ребра, называются полными графами. (рис.4)
Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным.
Стрелка от одной работы к другой на графе, изображенном на рисунке, означает последовательность выполнения работ.
Нельзя начинать монтаж стен, не закончив строить фундамент, чтобы приступить к отделке, нужно иметь на этажах воду и т. д.
Степени вершин и подсчет числа ребер.
Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.
На рисунке 5 изображен граф с пятью вершинами.
Степень вершины А обозначим Ст.А.
На рисунке:
Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.
Сформулируем некоторые закономерности, присущие определенным графам.
Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.
Закономерность 2. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.
Эта закономерность справедлива не только для полного, но и для любого графа.
Число нечетных вершин любого графа четно.
Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2.
Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.
Эйлеровы графы.
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. (рис.6)
Такими графы названы в честь учёного Леонарда Эйлера.
Закономерность 3. (вытекает из рассмотренной нами теоремы).
Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 4. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Закономерность 5. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.
Закономерность 6. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.
Связные графы.
Граф называется связным, если любые две его вершины могут быть соединены путем, т. е. последовательностью ребер, каждое следующее из которых начинается в конце предыдущего.
На рисунке 7, очевидно, изображен несвязный граф.
Граф называется несвязным, если это условие не выполняется.
Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным.(рис.8)
Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом.
Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа. (рис.8)
Несвязный граф состоит из нескольких «кусков». Эти «куски» называются компонентами связности графа. Каждая компонента связности является, конечно, связным графом. Отметим, что связный граф имеет одну компоненту связности.
Граф является эйлеровым тогда и только тогда, когда он связен и имеет не более двух нечетных вершин.
Деревья.
Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.
Циклом называется путь, в котором совпадают начало с концом.
Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом.
Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.9а).
В графе на рис.9б два цикла: 1-2-3-4-1 и 5-6-7-5.
Путем в графе от одной вершины к другой называется такая последовательность ребер, по которой можно проложить маршрут между этими вершинами.
При этом никакое ребро маршрута не должно встречаться более одного раза. Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец пути.
Висячей вершиной называется вершина, из которой выходит ровно одно ребро (рис.10).
(кружком обведены висячие вершины).
Для каждой пары вершин дерева существует единственный путь, их соединяющий.
Этим свойством пользуются при нахождении всех предков в генеалогическом дереве, например, по мужской линии, любого человека, чья родословная представлена в виде генеалогического дерева, которое является «деревом» и в смысле теории графов.
Всякое ребро в дереве является мостом.
Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.
Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом.
(о висячей вершине). В каждом дереве есть висячая вершина.
. В дереве число вершин на одну больше числа ребер.
Изоморфизм. Плоские графы и теорема Эйлера.
Докажем, что графы изображенные на рисунке 11 изоморфны. 
Пронумеруем вершины первого и второго графов от 1 и до 4 (рис.12).
В первом графе соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4; заметим, что во втором графе также соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4, следовательно, данные графы изоморфны.
Для того, чтобы выяснить, изоморфны ли два графа, нужно убедиться в том, что у них:
- одинаковое количество вершин
- если вершины одного графа соединены ребром, то и соответствующие им вершины другого графа тоже соединены ребром.
Граф, который можно нарисовать так, чтобы его рёбра не пересекались нигде, кроме вершин, называются плоским или планарным.
Эйлера. Для правильно нарисованного связного плоского графа имеет равенство: V-E+F=2, где V – число вершин, E — число рёбер, F – число кусков.(равенство V -E+F=2 обычно называют формулой Эйлера).
Граф, каждая вершина которого соединена с ребром любой другой вершины, называется полным.
Понтрягина – Куратовского. Граф является плоским тогда и только тогда, когда он не содержит (в топологическом смысле) графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами.
(В основном используется в старинных задач о домах и колодцах, суть которой сводится к выяснению вопроса — является ли рассматриваемый граф плоским или нет, рис.13)
Ориентированные графы.
Так, например, схема дорог и площадей города изображается с помощью плоского графа. Но если нужно этой схемой воспользоваться с целью проезда по городу на автомашине, а движение на отдельных (или на всех) улицах одностороннее?
Тогда могут помочь сориентироваться в этой ситуации стрелки, расположенные, например, прямо на ребрах — улицах рассматриваемой схемы (графа) города.
Граф, на рёбрах которого расставлены стрелки, называется ориентированным.
Степенью выхода вершины ориентированного графа называется число ребер, для которых эта вершина является началом (число ребер, «выходящих» из вершины).
Степенью входа вершины ориентированного графа называется число ребер, для которых эта вершина является концом (число ребер, «входящих» в вершину).
Так, на рисунке 15 изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие:
Ст.вх.А=2, Ст.вых.А=1 Ст.вх.В=2, Ст.вых.В=0 Ст.вх.Д=1, Ст.вых.Д=3.
Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер A1A2, A2A3, . Аn-1Аn, в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз.
На рисунке.15 показаны примеры путей в ориентированном графе. Причем, первые два пути простые — ни одна из вершин не содержится в нем более одного раза. Третий путь не является простым ,т. к. через вершину Г путь «проходил» дважды.
Ориентированным циклом называется замкнутый путь в ориентированном графе.
На рисунке 15 приведены примеры ориентированных циклов в последних двух графах. Цикл, как и любой другой путь в графе, имеет длину, которая определяется числом ребер в этом пути.
Так, на рисунке 16 пути от А к Д могут быть различны и иметь различную длину.
Первый путь имеет длину 2, второй — 3,
а третий — 4.
Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними. Так расстояние между вершинами А и Д на графе рисунка 16 равно 2; записывают так: S(АД)=2.
Если в ориентированном графе нельзя «пройти» от одной вершины до другой, то расстояние между ними называют бесконечным(обозначают значком бесконечности). Так, расстояние между вершинами Б и Д графа, представленного на рисунке 17 бесконечно: S(БД) = ∞
Ориентированные графы в экономике активно используются в сетевом планировании, в математике — в теории игр, теории множеств; при решении многих задач, в частности, комбинаторных.
Основные понятия теории графов. Изолированная и висячая вершина. Основные задачи теории графов. Проблемы надежности
Если связь имеет направление, то она называется дугой , иначе ребром .
Если все связи графа дуги, то такой граф называется ориентированным – орграфом, если ребра неографом.
Если в графе присутствуют и ребра и дуги – граф называют смешанным.
Две вершины называются смежными если они соединены ребром или дугой.
Две связи называются смежными если они имеют общую вершину.
Вершина xi инцидентна uij если она является началом или концом uij.
Ребро / дуга uij инцидентна xi если она входит или выходит из этой вершины.
Число дуг/ребер, инцидентных вершине xi называется степенью этой вершины ρ(xi).
Для неографа ∑(i=1 до |x|)ρ(xi)=2|V|.
Геометрически граф представляет собой множество точек и множество кривых, соединяющих эти точки.
ρ(х1)=3 ρ(х2)=ρ(х3)=2 ρ(х4)=1 ρ(х5)=0
Вершина, не имеющая инцидентных ребер (дуг) называется изолированной ρ(хi)=0.
Вершина, инцидентная только одному ребру/дуге называется висячей.
Граф, в котором перемещаясь от вершины к вершине можно попасть в любую вершину называется связным, иначе – несвязным.
Граф в котором все вершины попарно смежны – полный Kn.
n – количество вершин. Для полного графа |V|=(n(n-1))/2
Граф, имеющий кратные ребра называется мультиграфом.
Граф, в котором опущены некоторые ребра, а число вершин осталось прежним, называется частичным или суграфом.
Граф в котором опущены некоторые вершины и инцидентные им ребра, называется подграфом.
Граф имеющий кратные ребра и петли, называется псевдографом.
Если вершины графа можно разбить на два непересекающихся подмножества x1∩x2=0 так, что не существует ребер, соединяющих вершину из х1 с вершиной х2, то такой граф называется двудольным, бихроматическим, Кёнига.
Полный двудольный граф: все вершины из х1 связаны со всеми вершинами из х2: К3,3,
Графы называются изоморфными если у них одинаковое количество вершин и каждой паре вершин, соединенных в одном графе, соответствует пара вершин, соединенных в другом.
Последовательность ребер графа, в котором любая пара соседних ребер имеет одну и ту же инцидентную вершину – маршрут.
Маршрут, в котором все ребра различны – цепь.
Маршрут, для которого различны все вершины – простая цепь.
Замкнутая цепь – цикл, замкнутая простая цепь – простой цикл.
Цикл, в котором содержатся все ребра – Эйлеров цикл. Необходимое и достаточное условие его существования – четкость степеней всех вершин.
Простой цикл, который проходит через все вершины, называют гамильтоновым циклом..
Достаточное условие существования:
1. если в графе с n вершинами для любой пары вершин xi, xj выполняется условие: ρ(xi)≥n, то в таком графе существует Гамильтонов цикл.
2.В графе существует гамильтонов цикл, если для любой вершины xi выполняется условие ρ(xi)≥n/2
Несвязный граф без циклов, отдельные компоненты которого являются деревом – лес.
Связный граф без циклов — дерево
Любое дерево, построенное на n вершинах содержит (n-1) ребер; а лес, состоящий из n вершин, р деревьев, содержит (n-p) ребер.
Число различных деревьев связанного помеченного графа равно n n -2 /
Для n=4: n n -2 =16
Различают два крайних дерева: последовательное и звездное.
Дерево может быть выделено из любого графа, если оно содержит все вершины графа (это остов или покрывающее дерево)
Каждый граф обладает свойствами, которые оцениваются хар-ческими числами:
1. Цикломатическое число υ(G) – число ребер, которые необходимо удалить из графа, чтобы он стал деревом (или лесом, если граф был несвязным)
K=|U| — число ребер графа
|T|=n-1 – чмсло ребер дерева
υ(G)=k-n+p (если дерево)
2. Хроматическое число K(G) – наименьшее число непересекающихся подмножеств вершин, на которые можно разбить вершины графа так, чтобы ребра графа соединяли вершины только разных подмножеств. (только разноокрашенные вершины)
Граф называется плоским, ели он расположен на плоскости так, что ребра имеют общие точки лишь в вершинах.
Граф, изоморфный плоскому, но имеющий пересечения ребер, называется планарным.
Непланарный граф нельня нарисовать на плоскости без пересечений.
Планарность – свойство, плоскость – его реализация.
Операция расширения графа – замена одного ребра uij на 2: uip и upj с введением вершины р. Операция сжатия – обратная.
Исходный, расширенный и сжатый графы изоморфны с точностью до вершины i-ой степени.
Основные понятия графов
Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач. В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Мы же обсудим только самые основные понятия, свойства графов и некоторые способы решения задач.
Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
Теперь сразу видно, что долететь с Земли до Марса нельзя.
Решение этой двух задачи – графическое представление. Она состоит из несколько точек, некоторые из которых соединены линиями. Такие картинки и называются графами. Точки при этом называются вершинами, а линии – ребрами графа.
Графом G(V,X) называется пара двух конечных множеств: множества точек и множества линий, соединяющих некоторые пары точек. Точки называются вершинами графа и обозначаются А,В,С и т.д., линии – ребрами графа и обозначаются а,в,с, х1,х2,х3 и т.д.
Виды графов
Если в графе все ребра не имеют порядка (то есть ребра не имеют стрелок), то граф называется неориентированным.
Рисунок 1 – Неориентированные графы
Если все ребра в графе являются упорядоченными (то есть ребра имеют стрелки), то граф называется ориентированным. В нем ребра называются дугами.
Рисунок 2 – Ориентированные графы
Дуга у ориентированного графа, как у вектора, имеет направление, то есть имеет начало и конец. Начало (где нет стрелки) называют выходом, конец (где есть стрелка) – входом. Это важные понятия.
Если в графе имеются и ребра и дуги (то есть и со стрелками и без стрелок), то граф называется смешанным.
Рисунок 3 – Смешанный граф
Легко найти примеры графов в самых разных областях науки и практики. Сеть дорог, трубопроводов, электрическая цепь, структурная формула химического соединения, блок-схема программы и др.
Основные понятия элементов графа
Рассмотрим основные понятия элементов графов. Эти понятия могут называться одинаково, но немного по-разному определятся в каждом виде графа. А в смешанном графе будут определяться двояко, как для ориентированного графа, так и для неориентированного. Чтобы рассмотреть подробнее все понятия, нарисуйте в тетради четыре графа – рис.1, рис.2, рис.4, рис.5
Рисунок 4 Рисунок 5
Инцидентность. Если ребро или дуга графа соединяет две его вершины, то говорят, что это ребро им инцидентно. Например, на рис.1 ребро r инцидентно вершинам D и B (так как соединяет их). На рис. 2 дуга s инцидентно вершинам C и A. На рис. 5 ребро а инцидентно вершинам А и В.
Смежность. Это понятие распространяется как на ребра и дуги, так и на вершины. Рассмотрим их подробнее.
Две вершины графа называются смежными, если существует инцидентное им ребро или дуга. Например, рис.1 смежные вершины – С и А, С и D, А и В, А и D; рис.2 смежные вершины – А и В, А и С, В и С.
Для неориентированного графа: два ребра называются смежными, если они имеют общую вершину. Например, рис.5 смежные ребра – c и d и e, a и b
Для ориентированного графа: две дуги называются смежными, если они имеют общих выход. Например, рис.2 смежные дуги – t и u
Петля. Ребро, у которого начало и конец совпадают, называют петлей и обозначается, например q(С,С), как в графе на рис.1 Петли могут быть и в ориентированном графе, как на следующем рисунке а(1,1) и с(2,2)
Кратность. Это понятие для каждого вида графа определятся немного по-разному.
Для неориентированного графа: ребра, имеющие одинаковые концы, называются кратными, например рис.1 кратные ребра — p и u; рис.5 кратные ребра — c и d и e, a и b.
Для ориентированного графа: дуги называются кратными, если они имеют одинаковые начальные и конечные вершины, т.е. имеют одинаковое направление, например, рис.2 кратные дуги — t(B,C) и u(B,C).
Степень вершин. Это понятие для каждого вида графа определятся немного по-разному.
Для неориентированного графа: число ребер, инцидентных одной вершине, называется степенью этой вершины и обозначается deg. Другими словами – количество ребер выходящих из одной и той же вершины будет считаться степенью этой вершины. Например, рис.1 степень вершины А записывается как deg(A)=3 (т.к. из А выходят 3 ребра), deg(D)=2. Для рис.5 deg(A)=5. Если в вершине петля, то она дает вклад в степень, равный 2 (т.к. ребро и выходит и входит в эту вершину), т.е. на рис.1 deg(С)=4.
Для ориентированного графа: находят полустепени входа и выхода дуг. Степень входа – это число дуг, для которых эта вершина является концом, т.е. на рис.2 deg+(A)=1 (+ — это вход дуги).
Степень выхода – это число дуг, для которых эта вершина является началом, т.е.рис.2 deg _(A)=1(- — это вход дуги). Пример, рис.2 deg+(В)=1 deg _(В)=2; deg+(С)=2 deg _(С)=1.
Изолированная вершина. Вершина графа, имеющая степень, равную 0, называется изолированной. То есть, это та вершина, которая не соединяется ни с одним ребром или дугой. Например, рис.1 изолированная вершина – Е.
Висячая вершина. Вершина графа, имеющая степень равную 1, называется висячей. То есть, это та вершина, которая соединяется только с одним ребром или дугой. Например, рис.4 висячие вершины – Q, H, E, B, A.
Четность и нечетность вершин. Вершина называется четной (нечетной), если её степень – четное (нечетное) число. Например, рис.1 четные вершины – D и C (т.к. deg(D)=2 и deg(С)=4), нечетные вершины – А и В (т.к. deg(A)=3 и deg(В)=3).
Маршрут. Это понятие распространяется только на неориентированный граф.
Маршрут – это последовательность попарно инцидентных вершин неориентированного графа. То есть, это ряд вершин, которые соединяются ребрами и по ним можно пройти от начальной вершины к конечной. Например, рис.1 маршруты – ВАВDCCA, DВА; рис.4 маршрут – FDCH. Длина маршрута определяется количеством пройденных ребер, например, длина маршрута DВА=2, длина маршрута FDCH=3.
Путь. Это понятие распространяется только на ориентированный граф.
Путь – это упорядоченная последовательность дуг ориентированного графа, в которой конец предыдущей дуги совпадает с началом следующей и все дуги единственны. То есть, нельзя проходить дважды по одной и той же дуге. Например, рис.2 пути – rus, tsru. Длина пути определяется количеством дуг, то есть рис.2 длина пути rus=3, длина пути tsru=4.
Гамильтонов путь. Гамильтоновым путем графа называется путь, проходящий через каждую его вершину только один раз. Например, рис2 гамильтонов путь – ru или ts.
Эйлеров граф. Эйлеровым графом называется граф, который содержит все ребра графа только один раз. Он должен иметь не более двух нечетных вершин.
Теорема: В графе G(V, X) сумма степеней всех его вершин – число четное. Число нечетных вершин любого графа – четно. Невозможно начертить граф с нечетным числом нечетных вершин.