Способы задания графов
Способы задания графа. Изоморфные графы.
Графы могут задаваться следующими способами:
1) геометрическим способом – рисунки, схемы, диаграммы;
2) алгебраическим способом – перечислением вершин и ребер;
3) табличным способом;
4) матричным способом.
Человеку удобно работать с графом-рисунком, так как он может легко установить связь между вершинами в наглядном виде с помощью ребер, изображаемых непрерывными линиями. Такое геометрическое представление плоского графа называется его реализацией.
Для машинной обработки удобнее задать граф в алгебраической форме – перечислением (списком) вершин или ребер.
При переходе от алгебраического способа к геометрическому одному и тому же графу могут соответствовать различные изображения – изоморфные графы,при этом от правильного изображения зависит, например, свойство плоской реализуемости. Для этого нужно правильно задать сам граф.
Основным способом задания графа является перечисление всех его вершин и ребер. Но такое представление, во-первых, несимметрично, во-вторых, для указания каждого ребра нужно еще раз выписывать соответствующие вершины, что плохо с точки зрения сжатия и хранения информации.
При задании графа таблицейсоставляется таблица,состоящей из 
строк (вершины) и т 
столбцов (ребра). На пересечении строк и столбцов пишутся соответствующие знаки, которые показывают отношение (инцидентность) вершины и ребра. Это может быть знаки “+” и “-”, числа 0,1,-1 и др.
Главным во всех способах задания графа (диаграммой, матрицей, таблицей) является указание соответствия между множествами 
вершин 
t к 
ребер 
.
Пусть дан граф 
,где 
– вершины, а 
– ребра, среди которых могут и кратные ребра (есть вершины, которые соединяет несколько ребер).
Матрицей инцидентностиданного графа будет таблица, состоящая из строк (вершины) и 
столбцов (ребра).
При рассмотрении неориентированного графа на пересечении строк и столбцов ставится число 1, если соответствующие вершина и ребро инцидентны и ставится число 0, они не инцидентны.
При рассмотрении ориентированного графа на пересечении строк и столбцов ставится число 1, если из вершины выходит соответствующее ее ребро. Если в вершину входит ребро, то ставят число -1. Если вершина не инцидентна ребру, то ставится число 0.
Очевидно, что в каждом столбце матрицы инцидентности должно быть только два ненулевых числа, так как ребро инцидентно двум вершинам. Число ненулевых элементов каждой строки – степень соответствующей вершины.
Матрицы инцидентности прямоугольные, если число строк и столбцов различно. Если число вершин и ребер в графе одинаковое, то получается квадратная матрица.
Матрицу можно сделать квадратной для любого графа без кратных ребер. В таких случаях строки и столбцы изображают вершины. На пересечении строк и столбцов ставится число 1, если соответствующие вершины соединены ребром и ставится число 0, если вершины не соединены.
Для неориентированного графа ребраодновременно принадлежат или не принадлежат графу, так как символизируют одно и то же ребро. Матрица смежности неориентированного графа является симметрической и не меняется при транспонировании.
Хотя формально каждая вершина всегда смежная сама с собой, в матрице смежности мы будем ставить 0, если у нее нет петли, и 1, если есть одна петля.
Если граф имеет матрицу смежности и не имеет петель, на главной диагонали у него всегда стоят нули.
Пример.Составить таблицу инцидентности для орграфа, который имеет 3 вершины и 4 ребра.
| Вершины | Ребра | ||
| s | t | г | и |
| V1 | -1 | ||
| V2 | -1 | ||
| V3 | -1 | -1 |
Граф называется взвешеннымили сетью,если каждому его ребру поставлено в соответствие некоторое число. Взвешенными графами могут быть схемы в электронике, электрические схемы, карты автомобильных и железных дорог и др. Например, на картах автодорог вершины являются населенными пунктами, ребра – дорогами, а весом – числа, равные расстоянию между населенными пунктами.
В основе процесса планирования лежит некоторый сценарий, представляющий собой сеть, состоящую из вершин – пошагового описания действий и дуг – отношений между ними. Такой граф дает возможность, сравнивая альтернативы, планировать действия для достижения поставленной цели.
Понятия-объекты и другие элементы предметной области могут быть графически изображены в виде вершин, а отношения между ними – в виде дуг, связывающих эти вершины.
Источник
Графы
Содержание
В этом разделе курса мы рассматриваем понятие графа. В последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Это проблемы проектирования интегральных схем и схем управления, исследования автоматов, логических цепей, блок-схем программ, экономики и статистики, химии и биологии, теории расписаний и дискретной оптимизации.
1 Основные понятия
В дальнейшем, если это явно не оговаривается, мы будем рассматривать только простые графы.
Способы задания графа
- Явное задание графа как алгебраической системы.
- Геометрический
- Матрица смежности
- Матрица инцидентности
Рассмотрим различные способы задания для одного и того же графа.
a,b,c,d >, < u,v,w,x >; <( u,a ),( u,b ),( v,b ),( v,c ),( w,c ),( w,a ),( x,c ), ( x,d )>>. Так как мы рассматриваем только простые графы, граф нам проще определять как модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин. Тогда данный граф запишется как a,b,c,d > ; <( a,b ), ( b,a ),( b,c ),( c,b ),( a,c ),( c,a ),( c,d ),( d,c )>>. В таком представлении ребру соответствуют две пары вершин ( v 1 ,v 2 ) и ( v 2 ,v 1 ), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин – его мы и будем отождествлять с ребром. Для данного графа рёбра задаются множеством << a,b >,< b,c >,< a,c >,< c,d >> и граф мы будем записывать как пару ( V,E ), где V – множество вершин, а E – множество рёбер.
В дальнейшем мы будем опираться именно на второе определение графа.
Геометрический
3. Матрица смежности
| a | b | c | d | |
|---|---|---|---|---|
| a | 0 | 1 | 1 | 0 |
| b | 1 | 0 | 1 | 0 |
| c | 1 | 1 | 0 | 1 |
| d | 0 | 0 | 1 | 0 |
4. Матрица инцидентности
| u | v | w | x | |
|---|---|---|---|---|
| a | 1 | 0 | 0 | 0 |
| b | 1 | 1 | 1 | 0 |
| c | 0 | 1 | 0 | 1 |
| d | 0 | 0 | 1 | 1 |
Понятие изоморфизма для графов имеет наглядное толкование. Представим рёбра графов эластичными нитями, связывающими узлы – вершины. Тогда, изоморфизм можно представить как перемещение узлов и растяжение нитей.
Пример 1 (изоморфизм). Покажем, что следующие два графа изоморфны.
Действительно, отображение a ® e, b ® f, c ® g, d ® h , являющееся изоморфизмом легко представить как модификацию первого графа, передвигающую вершину d в центр рисунка.
1.1 Постройте изоморфизм графов
Определение 1 (Степень вершины).
Степенью вершины назовём удвоенное количество петель, инцидентных этой вершине плюс количество остальных инцидентных ей рёбер.
1.2 Докажите, что изоморфизм сохраняет степени вершин графа. Иначе говоря, степень образа вершины при изоморфизме совпадает со степенью самой вершины.
1.3 Проверьте, изоморфны ли графы. см. Указания
1.4 Докажите, что сумма всех степеней вершин графа равна удвоенному количеству рёбер.
1.5 Докажите, что в любом графе количество вершин нечётной степени – чётное число. см. Указания
Подграфы
Определение 2 (Подграф). Подграфом графа называется граф, являющийся подмоделью исходного графа. Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).
Определение 3 (Подграф, порождённый множеством вершин).
Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого – U , содержащий те и только те рёбра, оба конца которых входят в U .
Определение 4 (Остовной подграф). Подграф называется остовным подграфом , если множество его вершин совпадает с множеством вершин самого графа.
Два последних определения дают два вида максимальности подграфов: максимальность множества вершин и максимальность множества рёбер. Это подтверждают следующие три задачи:
1.6 Докажите, что подграф H графа G является порождённым множеством своих вершин тогда и только тогда, когда не существует ни одного другого подграфа графа G, для которого H являлся бы остовным подграфом.
1.7 Докажите, что подграф H графа G является остовным тогда и только тогда, когда не существует ни одного другого подграфа графа G, для которого H являлся бы подграфом, порождённым множеством своих вершин.
1.8 Докажите, что если подграф является остовным подграфом и подграфом, порождённым множеством своих вершин одновременно, то этот подграф – сам граф.
Определение 5 (Пустой, полный графы). Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежны.
1.9 Докажите, что граф является пустым тогда и только тогда, когда все его подграфы – тоже пустые.
1.10 Докажите, что граф является полным тогда и только тогда, когда все его подграфы, порождённые некоторым множеством вершин – тоже полные.
1.11 Докажите, что полные (пустые) графы изоморфны тогда и только тогда, когда они имеют одинаковое количество вершин.
1.12 Докажите, что пустой граф с n вершинами содержит ровно n попарно неизоморфных подграфов.
1.13 Докажите, что граф с n вершинами является пустым тогда и только тогда, когда он содержит ровно n попарно неизоморфных подграфов.
1.14 Докажите, что полный граф с n вершинами содержит ровно n попарно неизоморфных подграфов, порождённых некоторыми множествами вершин.
1.15 Докажите, что граф с n вершинами является полным или пустым тогда и только тогда, когда он содержит ровно n попарно неизоморфных подграфов, порождённых некоторыми множествами вершин.
2 Маршруты, цепи и циклы
Маршруты, цепи и циклы
Определение 6 (Маршрут). Маршрутом в графе G = называется последовательность вершин и рёбер вида v 0 ,e 1 ,v 1 ,e 2 , . v n- 1 ,e n ,v n , где v i О V, i О [0 ,n ], e i О E, ( v i- 1 ,e i ), ( v i ,e i ) О I, i О [1 ,n ]. Вершины v 0 , v n называются связанными данным маршрутом (или просто связанными ). Вершину v 0 называют началом , а v n – концом маршрута. Если v 0 = v n , то маршрут называют замкнутым . Число n называется длиной маршрута .
Определение 7 (Цепь, простая цепь, цикл). Маршрут, в котором все рёбра попарно различны, называется цепью . Замкнутый маршрут, являющийся цепью, называется циклом . Маршрут, в котором все вершины попарно различны, называется простой цепью . Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом .
Пример 2 (цепь). Маршрут a, < a,b >,b, < b,c >,c, < c,a >,a, < a,d >,d в первом графе из примера 1 является цепью, но не является простой цепью.
Замечание. Мы будем отождествлять циклы, являющиеся циклическими перестановками друг друга.
2.1 Докажите, что изоморфизм сохраняет циклы графа.
2.2 Вернитесь к задаче 1.3 и получите для неё более простое решение. см. Указания
Графы часто используют для изображения различных отношений (например, иерархических отношений, т.е., на языке математики – отношений частичного порядка). Правда, для точного представления таких графов необходимо выразить понятие направления на графе. Мы не будем сейчас вводить новые понятия, а будем просто использовать расположение вершин на рисунках (одна выше или ниже другой).
Пример 3 (граф отношения делимости). Построим граф, изображающее отношение делимости на множестве <1,2,3,4,5,6,7,8,9,10>. Принцип такой: если от одного числа до другого есть цепь, ведущая вверх, тогда второе число делится на первое.
Связность графа
Определение 8 (Связность). Граф называется связным , если любая пара его вершин связана.
2.3 Покажите, что отношение связанности вершин является отношением эквивалентности. см. Указания
Определение 9 (Связные компоненты). Связными компонентами графа называются подграфы данного графа, вершины которых являются классами эквивалентности отношения свзанности в данном графе.
2.4 Докажите, что связная компонента является связным графом.
Определение 10 (Цикломатическое число). Цикломатическим числом графа называется число связных компонент графа плюс число рёбер минус число вершин.
Эйлеровы и гамильтоновы циклы
Определение 11 (Эйлеров цикл). Эйлеровым называется цикл, проходящий по каждому ребру графа ровно один раз. Граф, имеющий эйлеров цикл, тоже будем называть эйлеровым.
Пример 4 (эйлеров цикл). Построим эйлеров цикл для второго графа из задачи 1.1. Это h, < h,l >, l, < l,i >, i, < i,m >, m, < m,j >, j, < j,n >, n, < n,k >, k, < k,h >, h, < h,i >, i, < i,j >, j, < j,k >, k, < k,l >, l, < l,m >, m, < m,n >, n, < n,h >, h .
Теорема 1 (Критерий эйлеровости графа). Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин – чётные числа.
Требование связности в теореме естественно – несвязный граф может быть эйлеровым только в том случае, если только одна связная компонента содержит рёбра. *
2.5 Какие из графов, упоминающихся в задачах и примерах являются эйлеровыми ?
Кроме понятия эйлерова цикла в задачах часто возникает необходимость нахождения цепи, проходящей по каждому ребру ровно один раз (снимается требование замкнутости. Такие цепи будем называть эйлеровыми цепями .
2.6 Докажите, что в связном графе существует эйлерова цепь тогда и только тогда, когда граф содержит не более двух вершин нечётной степени. см. Указания
Определение 12 (Гамильтонов цикл). Гамильтоновым называется цикл, проходящий по каждой вершине графа ровно один раз.
2.7 Все ли графы, упоминающиеся в задачах и примерах содержат гамильтонов цикл ?
2.8 Содержит ли гамильтонов цикл граф ромбического додекаэдра:
Деревья
Определение 13 (Дерево). Связный граф без циклов называется деревом .
Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярны генеологические деревья.
Пример 5 (генеологическое дерево). На рисунке показано библейское генеологическое дерево.
2.9 Докажите, что граф является деревом тогда и только тогда, когда любая пара различных вершин соединена единственной цепью.
2.10 Докажите, что граф является деревом тогда и только тогда, когда он связен, но после удаления любого ребра становится несвязным.
2.11 Докажите, что количество рёбер дерева на единицу меньше количества вершин. см. Указания
Определение 14 (Лес, листья). Граф без циклов называется лесом . Вершины степени 1 в дереве называются листьями .
2.12 Докажите, что связными компонентами леса являются деревья.
2.13 Докажите, что цикломатическое число леса равно нулю. см. Указания
Деревья – очень удобный инструмент представления информации самого разного вида. Деревья отличаются общего случая от простых графов тем, что при обходе дерева невозможны циклы. Это делает графы очень удобной формой организации данных для различных алгоритмов. Таким образом, понятие дерева активно используется в информатике и программировании.
2.14 Найдите количество остовных подграфов, являющихся деревьями, в полных подграфах с 3 -мя, 4 -мя, 5 -ю, 6 -ю вершинами. см. Указания
3 Раскраска, плоские графы
Раскраска графов
Определение 15 (Раскраска). Раскраской графа G = ( V,E ) называется отображение c : V ® N . *
Определение 16 (Правильная раскраска). Раскраска называется правильной , если образы любых двух смежных вершин различны: c ( u ) № c ( v ), если ( u,v ) О I . Хроматическим числом графа называется минимальное количество красок, необходимое для правильной раскраски графа.
Пример 6 (раскраска). На следующем рисунке показана правильная раскраска.
3.1 Найдите хроматические числа графов, упоминающихся в задачах и примерах.
3.2 Докажите, что если в графе все циклы имеют чётную длину, то существует правильная раскраска этого графа в 2 краски.
3.3 Докажите, что для любого дерева хроматическое число не превосходит 2.
3.4 Покажите, что необходимым условием существования гамильтонова цикла в графе с хроматическим числом равным 2 является равенство количества вершин, раскрашенных в разные краски.
3.5 Вернитесь к задаче 2.8 (о ромбическом додекаэдре) и получите её решение исходя из предыдущей задачи.
Грани графа
Помимо использования в дискретной математике, графы находят применение и в непрерывной математике, особенно в топологии. При этом графы представляют геометрические объекты на некоторой поверхности (часто на плоскости или на поверхности сферы.)
Определение 17 (Плоский граф). Существует правило изображение графов на поверхности: рёбра графа должны пересекаться только своими концами, то есть в точках, представляющих вершины графа.
Для графа, который может быть изображён подобным образом на плоскости, существует название: плоский граф .
Определение 18 (Грань графа). Гранью графа , изображенного на некоторой поверхности, называется часть поверхности, ограниченная рёбрами графа.
Данное понятие грани, по-существу, совпадает с понятием грани многогранника. В качестве поверхности в этом случае выступает поверхность многогранника. Если многогранник выпуклый, его можно изобразить на плоскости, сохранив все грани. Это можно наглядно представить следующим образом: одну из граней многогранника растягиваем, а сам многогранник «расплющиваем» так
Источник
