Размещено на http://www.allbest.ru/

Федеральное бюджетное государственное образовательное учреждение высшего профессионального образования

Госуниверситет - учебно-научно-производственный комплекс

Кафедра «Автопласт»

Реферат

по дисциплине «Базы данных, знаний, экспертные системы»

Тема:

Графовые сети

Выполнил: Декопольский Д.А.

студент группы 41-АП

Проверил: Фёдоров Т.В.

Орёл 2014 г.

Содержание

1. Основные понятия и виды графов

2. Теория графов

3. Идеи, принципы и язык теории графов

4. Абстрактные графовые сети

5. Семантические графовые сети

1. Основные понятия и виды графов

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

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

Рис. 1

Это по сути граф. Пять компьютеров являются вершинами, а соединения (пути передачи сигналов) между ними - ребрами. Заменив компьютеры вершинами, мы получим математический объект - граф, который имеет 10 ребер и 5 вершин. Пронумеровать вершины можно произвольным образом, а не обязательно так, как это сделано на рисунке. Стоит отметить, что в данном примере не используется ни одной петли, то есть такого ребра, которое выходит из вершины и сразу же входит в нее, но петли могут встречаться в задачах.

Вот некоторые важные обозначения, используемые в теории графов:

G = (V, E), здесь G - граф, V - его вершины, а E - ребра;

|V| - порядок (число вершин);

|E| - размер графа (число рёбер).

В нашем случае (рис. 1) |V|=5, |E|=10

2. Теория графов

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

Началом теории графов считается 1736 год, когда Эйлер обнародовал свои знаменитые рассуждения о Кенигсбергских мостах. Затем около 100 лет рассуждения Эйлера о мостах оставались никому не нужными, а методы теории графов невостребованными практикой. Интерес к графам появился только в середине 19 века благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. С тех пор сфера применений теории графов непрерывно расширялась и сегодня она представляет собой мощную формальную систему, имеющую необозримое множество областей практического применения. Естественно, в одной лекции невозможно детально рассмотреть все аспекты теории графов. Поэтому мы поступим иначе и постараемся понять ее сущность, повторив ход рассуждений Эйлера о Кенигсбергских мостах.

Итак в Кенигсберге (ныне г. Калининград) течет река Неман. Она омывает два острова. Между берегами реки и островами во времена проживания в Кенигсберге Эйлера существовали 7 мостов, расположение которых показывает план на Рис. 2.

графовый абстрактный семантический компьютерный

Рис. 2

Задача Эйлера состояла в том, чтобы определить, можно ли выйдя из пункта С (или любого другого пункта) пройти каждый мост только по одному разу и вернуться в исходный пункт. Рассуждения и действия Эйлера в ходе решения этой задачи можно представить последовательностью следующих шагов: 1) мы рисуем план, 2) рисуем неориентированный граф, ассоциированный с берегами, островами и мостами, 3) абстрагируем ассоциированный с данными граф от его содержания (см. Рис. 2б ); это решающий шаг рассуждений, поскольку абстрактный граф можно ассоциировать с чем угодно, например, с площадями и улицами между ними, 4) формулируем следующую теорему - Конечный граф G является эйлеровым графом тогда и только тогда, когда:

а) Граф G связан

б) Все его локальные степени четные.

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

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

Рис. 3. Раскрывает сущность теории графов в наглядной и формальной формах

3. Идеи, принципы и язык теории графов

4. Абстрактные графовые сети

Объясним понятие "абстрактная графовая сеть" на примере абстрактной сети, с которой работал Эйлер, когда он решал и обобщал задачу о Кенигбергских мостах. На Рис. 4 показана абстрактная графовая сеть, изображающая структуру семи Кенигсбергских мостов, двух берегов и двух островов, а также структуру других систем, например, четырех площадей и семи улиц между ними. Графовая сеть помечена на рис. 3.а не буквами, как сеть на Рис. 1 в Лекции 6, а числами 1, 2, 3, 4. Эта графовая сеть абстрактная, поскольку ее вершинам и ребрам не присвоены данные о какой-либо реальной системе, например, данные о системе семи мостов. Вместо слов "сети присвоены данные", мы будем, иногда, говорить "на сеть навешаны данные" Математически абстрактная графовая сеть, показанная на Рис. 4а, полностью определяется следующими семью неориентированными парами: {1,2}₁, {1,2}₂, {1,3}, {2,3}, {3,4}, {2,4}₁, {2,4}₂. Как видим, абстрактная графовая сеть определяется набором ребер.

Рис 4

5. Семантические графовые сети