Книги и конспекты / Шпоры / 9
.pdf9.Графы. Ориентированные и неориентированные графы. Вершины, ребра, петли. Способы задания графа. Порядок и размер графа. Смежность, инциндентность. Степень вершины. Изолированная вершина, связный граф. Двудольный граф, цепь, цикл, простая цепь. Простой цикл. Полный граф. Изоморфизм.
Определение. Конечным графом G=(X,α) называется пара, где Х – конечное множество вершин, а α – бинарное отношение на Х.
|
|
|
|
aαb |
|
b |
a |
b |
c |
d |
|
||
bαc |
|
|
||||
b |
c |
d |
|
|
|
|
|
cαd |
|
|
|||
a |
|
a |
|
a |
d |
|
|
|
cαa |
||||
c |
|
|
|
|||
|
|
|
|
|
||
|
|
|
aαa |
|
c |
|
|
|
|
|
|
||
|
|
|
|
aαc |
|
|
X={a,b,c,d} aαa - петля
Порядок графа – число его вершин. Размер графа – число его ребер.
Если отношения симметричные: aαb↔bαa; aαc↔cαa; bαc↔cαb; cαd↔dαc, то такой граф называется неориентированным, в противном случае – ориентированным.
2 ребра смежные, если у них есть общая вершина. 2 вершины смежные, если у них есть общее ребро.
а и х инциндентные, если существует b такое, что х связывает а и b. Вершина графа изолирована, если нет ребер, инциндентных ей.
Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь.
Граф G=(х, α) двудольный, если X=X1 объединяется с X2: X1∩X2=пустое множество, т.е. граф,
множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.
x1…x4 – вершины. x1αx2 α… αx4 – набор таких вершин – цепь. Простая цепь – цепь, для которой xi ≠xj.
Цепь называется циклом, если x1 =xn Простой цикл – простая цепь, где x1 =xn
Граф называется полным, если все его вершины связаны с другими.
Два графа G=(х, α) и H=(y, β), |
называются изоморфными, если существует |
|
биекция : X→Y, |
; |
|
Изоморфные графы
Для того чтобы графы были изоморфными, необходимо, чтобы количество ребер у них было равно.