С. А. Турбекова русский язык. Самостоятельная работа


Понятие графа. Способы представления графа



Pdf көрінісі
бет21/219
Дата22.04.2022
өлшемі1,62 Mb.
#140426
түріУчебное пособие
1   ...   17   18   19   20   21   22   23   24   ...   219
Байланысты:
Адскова

Понятие графа. Способы представления графа
Граф – пара G = (V, E), где V – множество объектов произ-
вольной природы, называемых вершинами, а Е – семейство пар ei 
= (vil, vi2), vijOV, называемых 
ребрами. 
В общем случае множе-
ство V и (или) семейство Е могут содержать бесконечное число 
элементов, но мы будем рассматривать только конечные графы, 
т. е. графы, у которых как V, так и Е конечны. Если порядок эле-
ментов, входящих в ei, имеет значение, то граф называется 
ориен-
тированным, 
сокращенно – орграф, иначе – 
неориентированным. 
Ребра орграфа называются 
дугами. 
В дальнейшем будем считать, 
что термин «граф», применяемый без уточнений (ориентирован-
ный или неориентированный), обозначает неориентированный 
граф.
Если е = , то вершины v и и называются концами ребра. 
При этом говорят, что ребро е является смежным (инцидентным) 
каждой из вершин v и и. Вершины v и и также называются 
смеж-
ными (инцидентными). 
В общем случае допускаются ребра вида 
е = ; такие ребра называются 
петлями.
Степень вершины графа – это число ребер, инцидентных 
данной вершине, причем петли учитываются дважды. Поскольку 
каждое ребро инцидентно двум вершинам, сумма степеней всех 
вершин графа равна удвоенному количеству ребер: Sum(deg(vi), 
i=1…|V|) = 2 * |E|.
Вес вершины – число (действительное, целое или рациональ-
ное), поставленное в соответствие данной вершине (интерпрети-
руется как стоимость, пропускная способность и т. д.). Вес, длина 
ребра – число или несколько чисел, которые интерпретируются 
как длина, пропускная способность и т. д.
Путем 
в графе (или маршрутом в орграфе) называется чере-
дующаяся последовательность вершин и ребер (или дуг – в ор-
графе) вида v0, (v0,v1), v1…, (vn – 1,vn), vn. Число n называется 
длиной пути. Путь без повторяющихся ребер называется цепью, 
без повторяющихся вершин – простой цепью. Путь может быть 


29
замкнутым (v0 = vn). Замкнутый путь без повторяющихся ребер 
называется 
циклом 
(или контуром в орграфе); без повторяющихся 
вершин (кроме первой и последней) – простым циклом.
Граф называется связным, если существует путь между лю-
быми двумя его вершинами, и несвязным – в противном случае. 
Несвязный граф состоит из нескольких связных компонент (связ-
ных подграфов).
(


Достарыңызбен бөлісу:
1   ...   17   18   19   20   21   22   23   24   ...   219




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет