АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Пример 1. Если порядок концевых точек ребра е безразличен, то говорят, что е

Пусть дан граф G = (V,E). Ребро {u, v}ÎE обозначают uv. Говорят, что ребро uv соединяет вершины u и v, а вершины u и v являются концевыми для данного ребра.

Если порядок концевых точек ребра е безразличен, то говорят, что е – неориентированное ребро. Как уже говорилось, обозначается ребро е = {а,b}. Если этот порядок важен, то е называют ориентированным ребром – дугой. Обозначается в этом случае ориентированное ребро (дуга) е = (a,b), причём (a,b)¹(b,а). При этом а называют начальной вершиной дуги, а b – конечной вершиной. На рисунках дуги обозначают стрелками.

Граф, состоящий из неориентированных рёбер, называется неориентированным графом. Граф, состоящий из ориентированных рёбер, называется ориентированным графом, орграфом. Элементы множества Х графа G называются вершинами, как и в случае неориентированного графа, а элементы множества А – дугами орграфа. При геометрической интерпретации дуги графа обозначаются линиями со стрелками, направленными от первого элемента дуги ко второму. При этом первый концевой элемент дуги называется её началом, а второй (на который указывает стрелка) – её концом. Петлёй называется дуга, начальные и конечные вершины которой совпадают.

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

Чтобы перейти от ориентированного графа к неориентированному (получить его неориентированный двойник), надо пренебречь направлением дуг орграфа. Обозначается операция пренебрежения направлением дуг следующим образом: .

§ 2.2. Отношения и характеристики элементов графа

Между элементами графа существуют отношения инцидентности и смежности.

Ребро и вершина инцидентны друг другу, если вершина является концевой вершиной данного ребра, и не инцидентны в противном случае.

Две вершины смежны, если они инцидентны одному и тому же ребру.

Рёбра смежны, если они инцидентны одной вершине.

Заметим, что отношение смежности существует между однотипными элементами графа, а отношение инцидентности – между разнотипными.

С помощью графов очень удобно описывать структуры сложных объектов (систем). Вершины графа при этом символизируют элементы системы, а рёбра – наличие связей между её элементами. Ориентированные и неориентированные графы отличаются тем, что в неориентированных графах связи между элементами только фиксируются, тогда как в ориентированных графах стрелками указывается направление связи.

Для неориентированных графов существует понятие «окружение вершины». Пусть G = (V,E) – неориентированный граф, v_i – некоторая его вершина (v_iÎV). Окружением вершины v_i называется множество смежных ей вершин графа G; обозначается таким образом: N_G(v_i). Мощность множества N_G(v_i) называется степенью вершины v_i.

Для орграфов существуют понятия «полустепени исхода вершины» и «полустепени захода вершины».

Пусть G = (X,A) – ориентированный граф, x_i – некоторая его вершина (x_iÎX). Полустепенью исхода вершины x_i называется мощность множества концевых вершин тех дуг, для которых вершина x_i является начальной. Обозначается полустепень исхода a_О(x_i). Полустепенью захода вершины x_i называется мощность множества начальных вершин тех дуг, для которых вершина x_i является конечной. Обозначается полустепень захода a_t(x_i).

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

Дата добавления: 2015-09-27 | Просмотры: 398 | Нарушение авторских прав