Инструменты пользователя

Инструменты сайта


examination:diskretka:question9

Вопрос №9. Задание графа матрицами смежности и инцидентности, списком ребер. Критерий изоморфности графов через их матрицы смежности.

Табличное и матричное представление графов.

  • Табличное представление - представление графа списком ребер.

Список ребер имеет вид таблицы с 2-мя графами: в 1 графе - имена ребер; во 2 графе - списки вершин, инцидентных данному ребру.

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

Если ребро е ориентированно с началом v и концом w, то имена вершин должны образовывать упорядоченную пару.

Если ребро е неориентированно, то следует использовать фигурные скобки {v;w}, т.е. порядок записи вершин не имеет значения.

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

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

  • Матричное представление

Граф называется ориентированным или орграфом, если все его ребра, неявляющиеся петлями, являются ориентированными.

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

Замечание Помимо ориентированных и неориентированных графов существуют смешанные графы, у которых часть ребер ориентированы, а часть не ориентированы.

Ориентированность и неориентированность графа альтернативами не являются: имеются графы,являющиеся одновременно и ориентированными, и неориентированными.

Такие «странные» графы имеют только петли.

Представление графов дается в 2-х видах: для орграфов и для неорграфов. При этом наличие петель вносит новые неприятные вариации.

  • Матричное представление неорграфов

Матрица смежности

Пусть имеется неорграф Г, для удобства будем считать этот граф конечным( множества вершин и ребер конечны).

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

V={v1,…,vn}

Определяем по графу и по введенном нами упорядочении вершин матрицу А(Г) - квадратную n - го порядка назыв - ю матрицей смежности неорграфа Г.

Замечание Неорграф определяет однозначно свою матрицу смежности, если заранее задано упорядочение вершин графа.

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

Замечание По матрице смежности неорграф Г (при заданном упорядочении вершин) устанавливается почти однозначно: нельзя установит при переходе от матрицы к графу только имена ребер графа, поскольку в матрице эти имена отсутствуют.

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

Матрица инцедентности

Матрица инцидентности неорграфа - В(Г)

Чтобы построить матрицу В(Г) необходимо линейно упорядочить множество вершин и ребер графа Г.

Пусть множество вершин графа V={v1,…,vn}

множество ребер графа Е={е1,…,еm}

Матрица В имеет размер n x m, строки этой матрицы отвечают вершинам графа, а столбцы - ребрам.

элементы матрицы

Замечание 1. Приведенное нами определение матрицы инцидентности не является общепринятым, многие авторы там, где у нас стоит 2, пишут 1.

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

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

Смена нумераций вершин графа пиводит к перестановке строк и матрицы В, а смена нумерации ребер к к перестановке столбцов матрицы.

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

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

Матрица инцидентности полезными алгбраическими свойствами не обладает, является числовой формой списк ребер.

Существуют и другие более частные либо менее употребляемые способы задания графов.

На пример, если граф простой, т.е. любые две вершины связывают не более одного ребра, то матрица смежности такого графа - это матрица бинарного отношения, которые это граф определяет.

Перейдем к определению аналогичных представлений для орграфов

  • Табличное представление

Список ребер (дуг) орграфа представляет собой таблицу из 2 граф: в 1-ой графе последовательно перечисляются имена всех дуг графа. На соответствующей позиции во 2-ой графе указывается начало и конец данной дуги(т.к. дуга орграфа представляет собой по существу именованную упорядоченную пару вершин, то упомянутые начало и конец дуги рекомендовано записывать в виде упорядоченной пары).

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

Список дуг должен быть дополнен списком изолированных вершин.

  • Матричное представление орграфов

Матрица смежности

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

Замечание В общем случае по матрице смежности можно определить, к какому графу она относится.: неорграфу или орграфу. Если матрица смежности несимметрична, то к орграфу.

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

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

Как всегда по матрице смежности граф восстанавливается точностью до изоморфизма.

Матрица инцидентности

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

Чтобы отличит в матрице начало дуги от ее конца следует использовать несовпадающие элементы.

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

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

По матрице инцидентности , если строки и столбцы именованы именами вершин дуг графа, сам граф восстанавливается однозначно.

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

Отличить неориентированное ребро от ориентированных дуг не представляет сложности: для неориентированного ребра в столбце две 1, для ориентированного - -1 и +1.

В случае петель, т.к. есть 2 способа для записи петель, если петлю рассматривать как неориентированное ребро, она содержит 2, если как дугу - +1.

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

examination/diskretka/question9.txt · Последние изменения: 2014/01/15 08:14 (внешнее изменение)