Студопедия

КАТЕГОРИИ:

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


Определение: Вершина, инцидентная ровно одному ребру, и само ребро называются концевыми (иливисячими).




Определение: Степеньювершины vграфа G называется число v), равное числу ребер, инцидентных вершине v.

У изолированной вершины v) = 0.

У висячей вершины v) = 1.

Определение: Полустепеньюисхода вершины v в орграфе Дназывается число v), равное количеству дуг, исходящих из вершины v.

Определение: Полустепеньюзахода вершины v в орграфе Д называется число v), равное количеству дуг, заходящих в вершину v.

Кол-во вершин и ребер в графе G будем обозначать соответственно n(G) и m(G). Кол-во вершин и дуг в орграфе Д будем обозначать соответственно n(Д) и m(Д).

Утверждение 1. Для любого псевдографа G выполняется равенство:

.

Утверждение 2. Для любого ориентированного псевдографа Д выполняется равенство:

.

Определение: Подграфом графа G называется граф, все вершины и рёбра которого содержатся среди вершин и ребер графа G.

Определение: Подграфназывается собственным, если он отличен от самого графа.

Определение: Объединением графов G1=(V1, X1) и G2=(V2, X2) называется граф G=G1+G2=(V1 V2, X1 X2).

Определение: Пересечением графов G1=(V1, X1) и G2=(V2, X2), где V1 V2 0, называется граф G=G1 G2=(V1 V2, X1 X2).

Определение: Произведением графов G1=(V1, X1) и G2=(V2, X2) называется граф G=G1×G2=(V, X), для которого V=V1×V2 – декартово произведение множеств вершин исходных графов, а множество ребер X определяется следующим образом: вершины (u1, u 2) и (v1, v2) смежны в графе G тогда и только тогда, когда или u1=v1, а u2 и v2 смежны в графе G2, или u2=v2, а u1 и v1 смежны в графе G1.

Часто бывает важно определить, какие графы считаются различными, а какие не различаются. Обычно это связывают с понятием изоморфизма графов.

Определение: Два графа G1=(V1, X1) и G2=(V2, X2) называются изоморфными, если существуют взаимно однозначные отображения f и g, такие, что f: V1 ® V2 и g: X1 ® X2, сохраняющие инцидентность.

Обозначаются: G1 ~ G2.

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

G1~G2~G3

Определение: Последовательность вершин и ребер (дуг) графа G (орграфа Д) v1x1v2x2v3…xkvk+1(k 1) называется маршрутом (путём) из вершины v1 в вершину vk+1.

Определение: Длина пути (маршрута) равна количеству дуг (ребер) в последовательности (=k).

Определение: Вершина v1 называется началоммаршрута (пути), а vk+1 – концом. Остальные вершины называются внутренними.

Маршрут (путь) рассматривается как непрерывная траектория движения по вершинам и рёбрам графа.

Пример: v1x1v2x3v3x6v4 – маршрут из v1 в v4 длиной 3.

 

 

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

Определение: Цепь, в которой все вершины попарно различны, называется простойцепью.


Поделиться:

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





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