Студопедия

КАТЕГОРИИ:

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


Определение графа




Пусть дано непустое множество X, состоящее из элементов, называемых точками ( ), и на X задано множество отношений Т, позволяющих установить соответствие между каждым элементом множества Х и некоторым его подмножеством.

Каждая пара точек , множества Х, между которыми установлено отношение из множества Т, называется ребром.

Графом называется непустое множество Х и множество отношений Т;

обозначается G(X,T).

Граф называется конечным, если множество Х конечно.

Граф G(X,T) геометрически представляет собой непустое множество точек (вершин) и множество отрезков (ребер), концы которых принадлежат данному множеству точек.

 

Например:

 

 

 


Рис 1.

 

Ребра графа обозначают парой вершин ( ).

Вершины, не принадлежащие ни одному ребру графа, называются изолированными.

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

Две вершины называютсясмежными, если они соединены ребром, два различных ребра смежные, если они имеют общую вершину.

Ребро и любая из его вершин называются инцидентными.

Ребро графа G(X,T), у которого начальная и конечная вершины совпадают, называется петлей.

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

Существуют различные способы задания конечного графа G(X,T).

Пусть вершины графа, ребра графа.

 


Поделиться:

Дата добавления: 2015-07-26; просмотров: 54; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты