Клики. Алгоритм поиска клик.

Клика – некоторый подграф данного графа, являющийся полным графом, построенный на соответствующим количестве вершин.

клика

Кликовое число – кол-во вершин в наибольшей клике данного графа

кликовое число = 4

Хроматическое число любого графа больше или равно кликового числа

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

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