КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Практическое занятие №2.Графы
Любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними может быть описана графом. Связи между узлами(вершинами) (V), определенные неупорядоченными парами вершин графа, называются ребрами (E), а граф –неориентированным. Если пары вершин упорядочены, связи называются дугами
Число ребер, исходящих из вершины vi(петля учитывается дважды), называется валентностью (степенью вершины) и обозначается:d(vi). Если V и E конечные множества, то и граф им соответствующий называется конечным. Граф называется вырожденным, если он не имеет ребер. Неориентированный граф называется простым, если он не имеет петель и любая пара вершин соединена не более чем одним ребром. Графы отображаются на плоскости набором точек и соединяющих их линий или векторов. Грани могут отображаться и кривыми линиями, а их длина не играет никакой роли. Граф G называется планарным (плоским), если его можно отобразить в плоскости без пересечения его граней (рис. 5). Граф называется связным, если для любых двух вершин существует последовательность ребер их соединяющая (рис. 3), т.е. граф не имеет изолированных фрагментов (вершин, ребер). Граф называется полным, если любые две вершины соединены только одним ребром (рис.4). Если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2. Специальными видами графов являются деревья (рис. 6.)
Ребро (дуга) и любая из его вершин называются инцидентными. Принято говорить, что (дуга) ребро (u, v) соединяет вершины u и v. Если вершина не инцидентна ни одному ребру (дуге), то она называется изолированной (d(vi)=0), если принадлежит только одному ребру (дуге), то называется висячей (d(vi)=1). Основные положения о вершинах графа: 1. В графе G сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа, так как каждое ребро участвует в этой сумме ровно два раза. 2. Число нечетных вершин любого графа четно. 3. Во всяком графе с n вершинами, где n ³2, всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями. 4. Если в графе с вершинами n>2 две вершины имеют одинаковую степень, то в этом графе всегда найдется либо одна вершина степени 0, либо одна вершина степени n - 1. Два графа G1=(V1,E1) и G2=(V2,E2) называются изоморфными, если между их вершинами существует взаимно однозначное соответствие. Алгоритм распознавания изоморфизма двух графов G1(X, E)и G2(Y,E) 1. Если X ≠ Y, то графы не изоморфны. 2. Выписываем все элементы обоих графов, определяя пары (xi,xj) и (yi, yj) для каждого элемента, где xi, yi - число исходов для каждой вершины обоих графов, а xj, yj – число заходов. 3. Для каждого элемента x графа G1 ищем такой элемент y графа G2, что выполняется условие: число исходов x совпадает с числом исходов y, и число заходов x совпадает с числом заходов y. Найденные элементы x и y соединяем дугой, т.е. строим граф соответствия. Если соответствия нет, то графы неизоморфны. 4. Выписываем подстановку, которая переводит граф G1 в граф G2.
Примеры выполнения заданий 1. А Б Решение: А) d(v1)=2,d(v2)=3,d(v3)=3,d(v4)=2,d(v5)=3,d(v6)=3. Б) d(v1)=2,d(v2)=3,d(v3)=3,d(v4)=2,d(v5)=3,d(v6)=3.
2. Докажите, что графы G1(X1, E1) и G2(Y2, E2) изоморфны.
Решение:
В результате получим соответствие: Следовательно, графы G1(X, E) и G2(Y, E)изоморфны.
Дата добавления: 2014-12-16; Просмотров: 935; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |