Студопедия

КАТЕГОРИИ:

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



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




Читайте также:
  1. D) определение стратегии развития общества.
  2. D.определение стратегии
  3. I. Определение состава общего имущества
  4. II. Влияние начальной концентрации Н2О2 на период полупревращения. Определение порядка реакции.
  5. II. Определение модуля сдвига при помощи крутильных колебаний
  6. III. Определение константы равновесия и константы скорости реакции разложения перекиси водорода.
  7. III.Определение перерасчета индексация и корректировка размера пенсии.
  8. PR: понятие и определение.
  9. S-локус – определение белых пятен
  10. А. Определение фольклора

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

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

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

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

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

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

 

Например:

 

 

 


Рис 1.

 

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

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

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

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

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

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

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

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

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

 


Дата добавления: 2015-07-26; просмотров: 7; Нарушение авторских прав







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