1. Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество: количество подмножеств конечного множества

выполняется для некоторых пар элементов заданного множества V. В
соответствии с этим БО может быть представлено в виде графа с множеством
вершин V, у которого ориентированное ребро (А, B)

19. Две вершины v∈V и w∈V, где V – множество вершин
графа G, называются смежными, если они соединены
ребром.
Если вершина является концом ребра, то вершина и ребро называются инцидентными.
Если из графа G удалить одну или несколько вершин,
то будут удалены и выходящие из них ребра. Оставшиеся
вершины и ребра образуют подграф G′графа G [16].
Очевидно, что для всякого подграфа справедливы утвер-
ждения: V′⊆V и E′⊆E [16; 56], где V и E – множества
вершин и ребер графа G; V′и E′– множества вершин и
ребер подграфа G′. Из определения следует, что всякий
граф является подграфом самого себя.

20. Всякий изоморфный плоскому граф называется планарным, то есть граф называется планарным, если у него есть плоское изображение.
Пусть n – число вершин связного плоского графа G,
r – число его ребер и q – число граней. Тогда
n + q = r + 2.
Любой граф с числом вершин n = 1,2,3,4 является пла-
нарным. Если же n = 5, то всякий граф является планар-
ным за исключением полного, который не имеет плоского
представления. Обозначим такой граф символом G5.
Планарным является всякий двудольный граф с
числом вершин n = 2,3,4,5,6 за исключением полного
двудольного графа типа G3,3 (см. рис. 24 раздела 2), т. е.
граф G3,3 не имеет плоского представления.
Таким образом, не всякий граф является планарным.
21. Ориентированный маршрут(ормаршрут) – конечная чередующаяся последовательность вершин и дуг графа таких, что каждая дуга исходит из предыдущей вершины и заходит в последующую вершину a_i= (v_i-1 , v_i) :
Орцепь – ориентированный маршрут без повторяющихся дуг
Путь –цепь без повторяющихся вершин .
Связность ориентированных графов определяется в принципе так же, как и неориентированных, те есть без учета направления дуг. Специфичным для орграфа (или смешанного графа) является понятие сильной связности. Орграф называется сильным (или сильносвязным), если любые две его вершины достижимы друг из друга.