Основные понятия теории графов: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «## Основные определения Формальное определение: Графом $G$ называется пара множеств $G = (V,...»)
 
Строка 1: Строка 1:
## Основные определения
+
==Основные определения==
  
 
Формальное определение:
 
Формальное определение:
  
Графом $G$ называется пара множеств $G = (V, E$, где $V(G)$ — непустое конечное множество элементов, называемых **вершинами** графа, а $E$ — множество пар элементов из $V$ (необязательно различных), называемых **ребрами** графа. $E = \{(u , v)\ | u, v \in V\}$ — множество ребер графа $G$, состоящее из пар вершин $(u, v)$.  Ребро $(u, v)$ соединяет вершины $u$ и $v$.  
+
Графом $G$ называется пара множеств $G = (V, E$, где $V(G)$ — непустое конечное множество элементов, называемых вершинами графа, а $E$ — множество пар элементов из $V$ (необязательно различных), называемых ребрами графа. $E = \{(u , v)\ | u, v \in V\}$ — множество ребер графа $G$, состоящее из пар вершин $(u, v)$.  Ребро $(u, v)$ соединяет вершины $u$ и $v$.  
  
 
Простое определение:
 
Простое определение:
Строка 12: Строка 12:
  
 
Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах $N$ - количество вершин, а $M$ - ребер. Количество ребер, исходящее из вершины называют степенью вершины $d(v)$. Для вершины $a$ ребро $(a, b)$ называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10).  
 
Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах $N$ - количество вершин, а $M$ - ребер. Количество ребер, исходящее из вершины называют степенью вершины $d(v)$. Для вершины $a$ ребро $(a, b)$ называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10).  
 
### Теоретическое задание
 
Назовите степень 1-ой и 6-ой вершины и какие ребра инциденты им.
 
 
![1](http://gaskley.narod.ru/Discr/more_2/10.gif)
 
  
 
Если какие-то две вершины соединены более, чем одним ребром, то говорят, что граф содержит кратные ребра. Если ребро соединяет вершину саму с собой, то такое ребро называют петлей.
 
Если какие-то две вершины соединены более, чем одним ребром, то говорят, что граф содержит кратные ребра. Если ребро соединяет вершину саму с собой, то такое ребро называют петлей.
  
**Простой граф** не содержит петель и кратных ребер. Если не сказано ничего про наличие петель и кратных ребер, мы будем всегда считать, что граф простой.
+
Простой граф не содержит петель и кратных ребер. Если не сказано ничего про наличие петель и кратных ребер, мы будем всегда считать, что граф простой.
 
 
### Теоретическое задание
 
Сколько может быть рёбер в простом графе в $N$ вершинами?
 
 
 
 
 
![2](http://rain.ifmo.ru/cat/data/theory/unsorted/matroids-2004/graph.gif)
 
 
 
 
 
### Теоретическое задание
 
Найдите цикл размера 4 и петлю в этом непростом графе.
 
 
 
  
Также часто рассматривают **ориентированные графы** — это графы, у которых ребра имеют направление, а иначе граф – неориентированный.
+
Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный.

Версия 13:55, 26 сентября 2019

Основные определения

Формальное определение:

Графом $G$ называется пара множеств $G = (V, E$, где $V(G)$ — непустое конечное множество элементов, называемых вершинами графа, а $E$ — множество пар элементов из $V$ (необязательно различных), называемых ребрами графа. $E = \{(u , v)\ | u, v \in V\}$ — множество ребер графа $G$, состоящее из пар вершин $(u, v)$. Ребро $(u, v)$ соединяет вершины $u$ и $v$.

Простое определение:

Граф - это набор вершин (точек) и соединяющих их отрезков (рёбер).

![Примеры графа](http://i.imgur.com/vE0aVrE.jpg)

Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах $N$ - количество вершин, а $M$ - ребер. Количество ребер, исходящее из вершины называют степенью вершины $d(v)$. Для вершины $a$ ребро $(a, b)$ называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10).

Если какие-то две вершины соединены более, чем одним ребром, то говорят, что граф содержит кратные ребра. Если ребро соединяет вершину саму с собой, то такое ребро называют петлей.

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

Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный.