metod_15.03.04_atppp_moas_2016 (1016590), страница 9
Текст из файла (страница 9)
- такое представление называется укладкой графа.13.Доказано, что в 3-мерном пространстве любой граф можно предста-вить в виде укладки таким образом, что линии, соответствующие ребрам (дугам)не будут пересекаться во внутренних точках. Для 2-мерного пространства это,вообще говоря, неверно. Допускающие представление в виде укладки в 2-мерномпространствеграфыназываютплоскими(планарным).Другими словами, планарным называется граф, который может быть изображенна плоскости так, что его рёбра не будут пересекаться.14.Гранью графа, изображенного на некоторой поверхности, называ-ется часть поверхности, ограниченная рёбрами графа.Данное понятие грани, по - существу, совпадает с понятием грани многогранника.
В качестве поверхности в этом случае выступает поверхность многогранника. Если многогранник выпуклый, его можно изобразить на плоскости,сохранив все грани. Это можно наглядно представить следующим образом: однуиз граней многогранника растягиваем, а сам многогранник «расплющиваем» так,чтобы он весь поместился внутри этой грани. В результате получим плоскийграф. Грань, которую мы растягивали «исчезнет», но ей будет соответствоватьгрань, состоящая из части плоскости, ограничивающей граф.Таким образом, можно говорить о вершинах, рёбрах и гранях многогранника, а оперировать соответствующими понятиями для плоского графа.15.Пустым называется граф без рёбер.
Полным называется граф, в ко-тором каждые две вершины смежные.16.Конечная последовательность необязательно различных рёберE1,E2,...En называется маршрутом длины n, если существует последовательностьV1, V2, ... Vn необязательно различных вершин, таких, что Ei = (Vi-1,Vi ).17.Если совпадают, то маршрут замкнутый.18.Маршрут, в котором все рёбра попарно различны, называется цепью.19.Замкнутый маршрут, все рёбра которого различны, называется цик-лом. Если все вершины цепи или цикла различны, то такая цепь или цикл называются простыми.20.Маршрут, в котором все вершины попарно различны, называетсяпростой цепью.21.Цикл, в котором все вершины, кроме первой и последней, попарноразличны, называется простым циклом.22.Граф называется связным, если для любых двух вершин существуетпуть, соединяющий эти вершины.23.Любой максимальный связный подграф (то есть, не содержащийся вдругих связных подграфах) графа G называется компонентой связности.
Несвязный граф имеет, по крайней мере, две компоненты связности.24.Граф называется k - связным (k - реберно - связным), если удалениене менее k вершин (ребер) приводит к потере свойства связности.25.Маршрут, содержащий все вершины или ребра графа и обладающийопределенными свойствами, называется обходом графа.26.Длина маршрута (цепи, простой цепи) равна количеству ребер а по-рядке их прохождения. Длина кратчайшей простой цепи, соединяющей вершиныvi и vj в графе G, называется расстоянием d (vi, vj) между vi и vj.27.Степень вершины - число ребер, которым инцидентна вершина V,обозначается D(V).С помощью различных операций можно строить графы из более простых,переходить от графа к более простому, разбивать графы на более простые и т.д.Среди одноместных операций наиболее употребительны: удаление и добавление ребра или вершины, стягивание ребра (отождествление пары смежныхвершин), подразбиение ребра (т.е.
замена ребра (u, v) на пару (u, w), (w, v), где w- новая вершина) и др.Известны двуместные операции: соединение, сложение, различные видыумножений графов и др. Такие операции используются для анализа и синтезаграфов с заданными свойствами.28.Два графа G1=(V1;E1), G2=(V2;E2),называются изоморфными, еслисуществует взаимнооднозначное соответствие между множествами вершин V1 иV2 и между множествами рёбер Е1 и Е2, такое, чтобы сохранялось отношениеинцидентности.Понятие изоморфизма для графов имеет наглядное толкование. Представим рёбра графов эластичными нитями, связывающими узлы – вершины. Тогда,изоморфизм можно представить как перемещение узлов и растяжение нитей.Теорема 1.Пусть задан граф G=(V;E),где V - множество вершин, E - множество рёбер,тогда2[E]=Σ(V), т.е.
удвоенное количество рёбер равно сумме степеней вер-шин.Теорема 2. (Лемма о рукопожатиях)В конечном графе число вершин нечетной степени чётно.Теорема 3.Граф связен тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества так, чтобы обе граничные точки каждогоребра находились в одном и том же множестве.Расстоянием между двумя вершинами связногографаназываетсядлина кратчайшей цепи, связывающей эти вершины (в количестве рёбер).Свойства связных графов.1.Связный граф остается связным после удаленияребра тогда итолько тогда, когда это ребро содержится в цикле.2.Связный граф , имеющий К вершин , содержит по крайней мере К-1ребро.3.В связном графе любые две простые цепи максимальной длиныимеет по крайней мере одну общую вершину.4.В графе с N вершинами и К компонентами связности число рёбер непревышает 1/2(N-K)(N-K+1).5.Пусть у графа G есть N вершин .
Пусть D(G)- минимальная из степе-ней вершин этого графа . Тогда D(G) > 1/2 (N-1).29.Связный граф без циклов называется деревом.Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярные генеалогические деревья.Пример(генеалогическое дерево): На рисунке показано библейское генеалогическое дерево.Эквивалентные определения дерева.1.Связный граф называется деревом, если он не имеет циклов.2.Содержит N-1 ребро и не имеет циклов.3.Связный и содержит N-1 ребро.4.Связный и удаление одного любого ребра делает его несвязным.5.Любая пара вершин соединяется единственной цепью.6.Не имеет циклов и добавление одного ребра между любыми двумявершинами приводит к появлению одного и только одного цикла.Занятие 2 – практическое занятие № 10 (интерактивное).Построение матриц инцидентности и смежности.Матрица смежности — один из способов представления графа в виде матрицы.Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которойзначение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.Иногда, особенно в случае неориентированного графа, петля (ребро из i-йвершины в саму себя) считается за два ребра, то есть значение диагональногоэлемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.Матрица смежности простого графа (не содержащего петель и кратныхребер) является бинарной матрицейи содержит нули на главной диагонали.Пример неориентированного графа и соответствующей ему матрицысмежности A.
Этот граф содержит петлю вокруг вершины 1, при этом в зависимости от конкретных приложений элементному (как показано ниже), либо двум.может считаться равным либо од-Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) ивершина). Столбцы матрицы соответствуют ребрам, строки — вершинам.Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (ихинцидентность).В случае ориентированного графа каждой дуге <x,y> ставится в соответствие "-1" в строке вершины x и столбце дуги <x,y> и "1" в строке вершины y истолбце дуги <x,y>; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится "0".Графы, деревья и их свойства.Деревом называется связный граф без контуров (а значит, и без циклов).
Граф (несвязный), состоящий из нескольких деревьев иногда называют лесом.Напомним, что вершина в графе называется висячей, если ее степеньравна единице. Дерево должно обязательно иметь висячую вершину, так какесли бы степень всех вершин в дереве была бы больше или равна 2, то по самойпервой лемме граф должен иметь цикл, что противоречит определению дерева.Докажем сейчас следующую достаточно важную теорему.Теорема. Если граф G является деревом, то число его ребер (т) и числоего вершин (п) связаны соотношением т = п – 1.Доказательство этой теоремы проведем по индукции по числу вершин.
Если данный граф содержит всего 2 вершины, то в нем только 1 ребро, инужное соотношение выполнено. Пусть наше утверждение выполнено для любого дерева, число вершин которого строго меньше п, Докажем его для дерева G, содержащего п вершин. Возьмем висячую вершину дерева G и удалимее из графа (вместе с единственным ребром, выходящим из этой вершины). Тогда новый граф также является деревом: новый граф не содержит контуров(циклов), он остается связным. (Если бы новый граф оказался несвязным, то какие-то две вершины графа G были бы связаны между собой через удаленную(висячую) вершину.
В этом случае степень этой висячей вершины была быбольше или равна 2, что невозможно). Таким образом, новый граф является деревом, и по индукционному предположению для него число ребер меньшечисла вершин на единицу. Так как число вершин и число ребер нового графаотличается от числа вершин и ребер “старого” графа G на единицу, то дляграфа G также выполнено то же самое соотношение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
