Изоморфизм графов. Примеры.

кол-во неориентированных простых графов

кол-во ориентированных простых графов

Изоморфизм простых графов – графы G1 и G2 изоморфны если существует отображение ФИ из множества вершин V1 в V2 которые являются взаимно однозначными и сохраняют отношение смежности (в графе G1 имеется ребро х y = Е(число рёбер) принадлежащие множеству рёбер графа G1 тогда в графе G2 обязано быть ребро фи от х и фи от у, они должны принадлежать множеству рёбер графа G2 и наоборот)

графы G1 и G2 изоморфны

3. Содержание

   • Графы. Основные определения. Соотношения между количеством ребер и количеством вершин.
   • Изоморфизм графов. Примеры.
   • Пути, цепи, циклы.
   • Связность графов.
   • Эйлеров цикл. Определение, условие существования, алгоритм нахождения.
   • Гамильтонов цикл. Определение. Задача о коммивояжере.
   • Деревья.
   • ОстОвное дерево. Алгоритм Крускала.
   • Алгоритм поиска кратчайшего пути в графе.
   • Клики. Алгоритм поиска клик.
   • Раскраска графов. Алгоритмы раскраски.
   • Генерация случайных графов.