Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. I.Способы задания графов. Степени вершин, матрицы инцидентности и смежности.
  2. ВЛИЯНИЕ ЛИНИИ ПСИХОМАТРИЦЫ НА ЦИФРЫ
  3. Глоссарий логограмм – символических понятий матрицы.
  4. Задание №3. Решить систему уравнений с помощью обратной матрицы
  5. Законы смежности и повторяемости Давида Гартли. Мозговые вибрации как физиологическая основа появления идей у человека.
  6. ЗНАЧЕНИЕ ВТОРОЙ СТРОКИ ПСИХОМАТРИЦЫ
  7. Использование матриц смежности.

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

Матрица инцидентности A. По вертикали указываются вершины, по горизонтали - ребра. aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в вершину i входит ребро j. Если ребро - петля, то aij=2.

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

Матрица смежности - квадратная симметричная матрица. По горизонтали и вертикали - все вершины. Dij= число ребер, соединяющее вершины i,j.

Матрица Кирхгофа: bij=-1, если вершины i и j смежны, bij=0 если вершины i и j не смежны, bii=deg(i). Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0.

Понятия смежности, инцидентности, степени

Если x ={ v, w } - ребро, то v и wконцы ребра x.

Если x =(v, w) - дуга ориентированного графа, то vначало, wконец дуги.

Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x).

Вершины v, w называются смежными, если { v, wX.

Степенью вершины v графа G называется число d(v) ребер графа G, инцидентных вершине v.

Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.

Полустепенью исхода (захода) вершины v ориентированного графа D называется число d+(v) (d-(v)) дуг ориентированного графа D, исходящих из v (заходящих в v).

Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в d+(v), так и в d-(v).

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

Пусть D =(V, X) ориентированный граф, V ={ v 1,..., v n}, X ={ x 1,..., x m}.

Матрица смежности ориентированного графа D − квадратная матрица

A (D)=[ aij ] порядка n, где

Матрица инцидентности − матрица B (D)=[ bij ] порядка n ´ m, где

Матрицей смежности неориентированного графа G =(V, X) называется квадратная симметричная матрица A (G)=[ aij ] порядка n, где

.

Матрица инцидентности графа G называется матрица B (G)=[ bij ] порядка n ´ m, где

 

 


Дата добавления: 2015-10-13; просмотров: 207 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Шаг 2. Знакомство и принятие заказа.| ЗАКОНОДАВЧА ВЛАДА

mybiblioteka.su - 2015-2024 год. (0.006 сек.)