пользователей: 21212
предметов: 10450
вопросов: 177346
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


Неориентированный граф. Изоморфизм графов. Способы задания графов. Степень вершины графа. Лемма о рукопожатиях.

Неориентированный граф G — это упорядоченная пара G := (V, E), где V — это непустое множество вершин или узлов, а E — множество пар  неупорядоченных вершин, называемых рёбрами.

Изоморфные графы

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

Пусть существуют графы G1 и G2

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

Пример:

 

Если степенные последовательности графов различны, то графы не изоморфны. 

Степенная последовательность - перечень степеней всех вершин, записанных по восрастанию( убыванию).

Способы задания графа:

1.Задание графов матрицей смежности:

Матрица смежности – это квадратная матрица порядка p (количество вершин),  элемент которой,  стоящий в i строке и j столбце определяется по правилу:

image037.gif

ПРИМЕР

image039.gif

image041.jpg

2. Задание графов матрицей инцидентций.

Матрицей  инцидентции называется прямоугольная матрица размерности image043.gif (–  количество вершин, q – количество ребер), элемент которой стоящий в i строке и j столбце определяется по правилу:

image045.gif

                                             - для неориентированного графа.

image047.gif- для ориентированного графа.

ПРИМЕР

 

image049.gif

image051.jpg

Степень вершины — количество рёбер графа G,инцидентных вершине x.

Лемма о рукопожатиях - сумма степеней вершин любого графа равна удвоенному числу его рёбер.


18.06.2015; 00:47
хиты: 221
рейтинг:0
Точные науки
математика
логика и основания математики
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь