Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
Особенно широкое применение теории графов в таких областях прикладной математики, как программирование, теория конечных автоматов, в решении вероятностных и комбинаторных задач.1 . Основные понятия теории графов Граф представляет собой непустое конечное множество вершин V и ребер Е, оба конца которых принадлежат множеству V . Число вершин графа G обозначим р , а число ребер - q Граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром.Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Если в графе с n вершинами (n ? 2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0 , либо в точности одна вершина степени n-1 . Свойства степени ВЕРШИНЫМАРШРУТОМ в графе называется чередующаяся последовательность вершин и ребер, в которой любые два соседних элемента инцидентны: Если то маршрут замкнут , в противном случае открыт. Изоморфизм графов Два графа называются изоморфными, если между множествами их вершин существует биективное (взаимно-однозначное) соответствие, такое, что вершины соединены ребрами в одном из графов в том и только в том случае, когда соответствующие им вершины соединены в другом графе.Алгоритм распознавания двух графов и Подсчитываем число вершин каждого графа (число вершин должно совпадать, в противном случае графы неизоморфные). Объединением графов при условии, что называется граф множеством вершин которого является множество а множеством его ребер является множество Пересечением графов называется граф множеством вершин которого является множество а множеством его ребер - множество Суммой по модулю два графа при условии, что называется граф множеством вершин которого является множество а множеством его ребер - множество Другими словами, этот граф не имеет изолированных вершин и состоит только из ребер, присутствующих либо в первом графе, либо во втором, но не в обоих графах одновременно.9.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
