Лекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b )




НазваниеЛекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b )
Дата конвертации21.02.2013
Размер445 b.
ТипЛекция


Лекция 9 Отношения, графы

Определения

Определение. Пусть а и b — объекты.

Определение. Пусть а и b — объекты.

Через (а, b) обозначим упорядоченную пару, состоящую из объектов а и b, взятых в этом порядке.

Упорядоченные пары (а, b) и (с, d) называются равными, если а = с и b = d.

В противоположность этому {а, b}= {b, а}.

Определение. Декартовым произведением множеств A и B, обозначаемым через АхВ, называют множество {(а, b) | аА и bB}.

Пример. Пусть A = {1, 2} и В = {2, 3, 4}. Тогда

AхB = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4)}

Отношения

Определение. Пусть А и В —множества.

Отношением из А в В называется любое подмножество множества АхВ.

Если А = B, то говорят, что отношение задано, или определено, на А (или просто, что это — отношение на множестве A).

Если R — отношение из A в B и (а, b)R, то пишут аRb.

Aобласть определения отношения R,

В —множество его значений.

Определение. Отношение {(b, а) | (а, b) R} называется обратным к отношению R и часто обозначается через R-1.

Свойства отношений

Определение. Пусть A—множество и R — отношение на A. Отношение R называется
  • рефлексивным, если аRа для всех a из А,

  • симметричным, если аRb влечет bRa для a и b из A,

  • транзитивным, если аRb и bRс влекут аRс для а, b и с из A. Элементы а, b и с не обязаны быть различными.

Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности.

Важное свойство любого отношения эквивалентности R, определенного на множестве A, заключается в том, что оно разбивает множество A на непересекающиеся подмножества, называемые классами эквивалентности.

Графы

Определение.

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

Если R — несимметричное отношение,

то Gориентированный граф;

R — симметричное, то G —неориентированный граф.

Пример.

A={1, 2, 3, 4} , R = {(1, 1), (1, 2), (2, 3), (2, 4), (3, 4), (4, 1), (4, 3)}.

Пара (а, b)R называется дугой (или ребром) графа G.

Пара (а, b)R называется дугой (или ребром) графа G.

Говорят, что дуга выходит из вершины а

и входит в вершину b.

Если (а, b) — дуга, то говорят,

что вершина а предшествует вершине b,

а вершина b следует за вершиной a.

Вершина b смежна с вершиной a.

Определения.

Определения.

Последовательность вершин (а0, а1, ... ,аn), n≥1, называется путем (или маршрутом) длины n из вершины а0 в вершину аn, если для каждого 1≤in существует дуга, выходящая из вершины аi-1 и входящая в вершину аi.

Если существует путь из вершины а0 в вершину аn, то говорят, что аn достижима из а0.

Циклом называется путь (а0, а1, ...,аn), в котором а0 = аn.

Граф называется сильно связным, если для любых двух разных вершин а и b существует путь из a в b.

Степень вершины

Степенью по входу (полустепенью входа) вершины а назовем число входящих в нее дуг,

а степенью по выходу (полустепенью исхода)—число выходящих из нее дуг.

Если граф неориентированный, то степень вершины – это количество ребер, связанных с ней.

Ациклические графы

Ациклическим графом называется (ориентированный) граф, не имеющий циклов.

Вершину, степень по входу которой равна 0, назовем базовой.

Вершину, степень по выходу которой равна 0, назовем листом (или концевой вершиной).

Дуга и путь в ациклическом графе

Если (a, b) – дуга в ациклическом графе,

то a – прямой предок b,

b – прямой потомок a.

Если в ациклическом графе существует путь из a в b,

то a – предок b,

b – потомок a.

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

Пусть дан граф G= (V,E), N = |V|, M = |E|.

Матрица смежностей для графа G – это матрица A размера NхN, состоящая из 0 и 1, в которой A[i, j]=1 тогда и только тогда, когда есть ребро из узла i в узел j.

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

Матрица инцидентностей для графа G – это матрица B размера NхM, в которой :



Списки смежностей

Списком смежностей для узла v называется список всех узлов w, смежных с v.

Табличное представление списков смежностей



Односвязный граф

- Содержит одну компоненту связности

- Существует путь из любой вершины в любую другую вершину

- Существует путь из заданной вершины в любую другую вершину

- Содержит связный подграф, включающий все вершины исходного графа

- Содержит в качестве подграфа дерево, включающее все вершины исходного графа (такое дерево называется остовным)

- При произвольном делении его вершин на 2 группы всегда существует хотя бы 1 ребро, соединяющее пару вершин из разных групп.

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


Похожие:

Лекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b ) iconОпределение. Определение
Пусть на тело действует сила в 8Н. Стрелка указывает направление силы, а длина отрезка соответствует числовому значению силы
Лекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b ) iconТеория графов Основные определения
Пусть имеется множество вершин V={V1,V2,…,Vn} и пусть на нем задано бинарное отношение Г⊂V×V
Лекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b ) iconВолновой метод Пусть граф задан графически. Пусть граф задан графически
Изобразить все попарно неизоморфные 4-вершинные графы без петель и кратных ребер
Лекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b ) iconПусть кто-нибудь Пусть кто-нибудь
«Пусть кто-нибудь «Пусть кто-нибудь попробует вычеркнуть из математики степени, и он увидит, что без них далеко не уедешь»
Лекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b ) iconОпределение Определение 1
...
Лекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b ) iconКлассный час Урок мужества, посвящённый памяти воинам интернационалистам. Пусть история всех нас рассудит и оценку пусть каждому даст. Пусть о павших никто не забудет
Хазарское полчище, монгольская орда, наполеоновская армия, германский вермахт- все они искали мирового господства. У всех на пути...
Лекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b ) iconОсновные виды деятельности
Объекты, выполненные на кад г. Санкт-Петербурга Объекты, выполненные при строительстве транспортного обхода г. Луга
Лекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b ) iconНезнающие пусть научатся, а знающие пусть вспомнят ещё раз! Античный афоризм тест
Какой физический параметр определяет количество теплоты, выделяющееся при сгорании 1 кг вещества?
Лекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b ) iconКлеопатра кто же она? Внешность Шекспир
Помпей: «Но пусть уста твои, о Клеопатра, Украсятся всей прелестью любви; Пусть с красотой соединятся чары»
Лекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b ) iconОбъекты и субъекты решений. Объекты и субъекты решений
Виды и характеристики систем, в которых разрабатываются решения (технические, биологические и социальные системы.). Особенности управления...
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница