Поиск клік в графах

Поиск клік в графах

Курсовой проект студента Шеломанова Р.Б.

Кафедра загальної теорії систем і системного анализа

Московский державний університет економіки, статисти та информатики

Москва 1998

Введение

Для ілюстрацій умов і рішень багатьох завдань люди користуються графіками. За своєю суттю графіки є набором з багатьох точок і відрізків прямих що з'єднують ці точки. Постає питання: підпорядковуються чи графіки будь-яким законам й володіють вони якимись властивостями? Це запитання поставлений Д. Кенігом, що об'єднав все схематичні зображення, які з сукупності крапок і ліній, загальним терміном «граф» і розглянув граф як математичний об'єкт. Теорія графів набула свого використання у рішенні цілого ряду завдань. У моєму курсовому проекті розглядатимуть розділ теорії графів присвячений максимальним повним подграфам, тоесть клікам. Метою проекту є написання програми на мові програмування, що з заданого графа виділяла б кліку з заданим числом вершин.

Допустим заданий граф G=(Х, Г). Досить часто виникає завдання пошуку таких підмножин безлічі вершин Х графа G, які мають певним, наперед заданим властивістю. Наприклад, як і максимально можлива потужність такого підмножини P. S Í Х, котрій породжений подграф P. S є повним? Відповідь це питання дає кликовое число графа G. Ця кількість і пов’язана з нею підмножина вершин описує важливі струтурные властивості графа і має безпосередні докладання при проведення проектного планування дослідницьких робіт, в кластерному аналізі та про чисельні методах таксономії, паралельных вычмслениях на ЕОМ, під час розміщення підприємств обслуговування, а також джерел постачання та споживачів на енергосистемах.

Часть 1. Теоретична частина до курсовому проекту.

Глава1. Теорія графов

Понятие графа

Графом G (X, U) називається сукупність двох об'єктів деякого безлічі X і відображення цього безлічі у собі Г.

При геометричному поданні графа елементи безлічі Х зображуються точками площини і називаються вершинами графа. Лінії, що з'єднують будь-які пари точок x і y, у тому числі у є відображенням х, називаються дугами графа. Дуги графа мають напрям, позначуване стрілкою, спрямованої вістрям від елемента х для її відображенню у.

Вершины і лінії графа

Две вершини А і В є граничними вершинами дуги, якщо А— початок дуги, а В її конец.

Смежными називаються різні дуги, мають загальну граничную точку. Дві вершини х і у суміжні, якщо вони різняться існує дуга, що йде від, а такою в іншу .

Вершина називається ізольованій, якщо вона з'єднана дугами коїться з іншими вершинами графа.

Если дуга U виходить із вершини х чи заходить в х, то дуга U называется инцидентной вершині х, а вершини х инцидентной дузі U. Загальна кількість дуг, инцидентной вершині х, є ступенем вершини х Р (х). Вершини, ступінь яких Р (х)>2, називаються вузлом, а зі ступенем Р (х).