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

35. Двудольные графы. Методика проверки графа на двудольность.
Двудольный граф – это граф, множество вершин которого можно разбить на 2 не пересекающихся множества V1 и V2 (V1^V2=Ø; V1vV2=V), так что каждое ребро соединяет некоторую вершину из множества V1 с некоторой вершиной множества V2. Для того чтобы граф являлся двудольным необходимо выполнение 2х условий: 1) граф должен быть связным; 2) все его простые циклы должны иметь четную длину.
36. Изоморфные графы. Методика проверки графов на изоморфность.
Изоморфизм графов – это отношение эквивалентности графов. Изоморфным отображением одного неориентированного графа на другой называется взаимооднозначное отображение вершин и ребер 1-го графа на вершины и ребра другого графа, при котором сохраняется смежность вершин. 2 графа считаются изоморфными, если существует изоморфное отображение 1-го графа на другой.
37. Эйлеровы графы. Теорема Эйлера (критерий эйлеровости графа). Методика нахождения эйлерова цикла в эйлеровом графе.
Замкнутый маршрут называется Эйлеровым циклом, если он содержит все ребра графа и проходит через каждое ребро по 1 разу. Связный граф имеет Эйлеров цикл тогда и только тогда, когда каждая его вершина имеет четную степень. Граф называется Эйлеровым, если он имеет Эйлеров цикл.
38. Гамильтоновы графы.
Замкнутый маршрут называется Гамильтоновым циклом, если он содержит все вершины графа и через каждую проходит по одному разу. Для того чтобы граф имел Гамельтонов цикл, он не должен иметь петель и кратных ребер, и для двух его несмежных вершин сумма степеней не должна быть меньше числа вершин этого графа. Граф называется Гамильтоновым, если он содержит Гамильтонов цикл.
39. Деревья и их свойства.
Граф G называется деревом, если он является связным и для него невозможно указать ни одного простого цикла. Граф G, все компоненты связности которого являются деревья, называется лесом. Свойства деревьев: а) число ребер графа, являющегося деревом, ровно на 1 меньше числа вершин; б) граф G не содержит циклов, то есть, добавляя к нему ровно 1 ребро, получаем ровно 1 простой цикл, проходящий через добавленное ребро; в) пусть G дерево, тогда любая цепь в графе G будет простой; г) дерево называется остовным, если оно содержит все вершины графа.