В p align=center> Кафедра загальної теорії систем
та системного аналізу
В В
Курсовий проект
за курсом:
"Загальна теорія систем"
по темі:
В
"Пошук клік у графах"
В В В
Група: ДІ 102
Студент: Шеломанов Р.Б.
В В В
Керівник: Кацман В.Є.
В В В В
Москва 1998
В В В
содеражанію
В
Введення ---------------------------------------------- ----------------------------- 3
Частина 1 Теоретична частина до курсового проекту ------------------- 3
Глава 1 Теорія графів ------------------------------------------- ---------- 3
Глава 2 Максимальні повні підграфи (кліки) ---------------------- 8
Частина 2 Практична реалізація курсового проекту --------------- 8
Завдання ---------------------------------------------- ----------------------- 8
Рішення ---------------------------------------------- ---------------------- 8
Висновок ---------------------------------------------- ------------------------- 12
Список літератури --------------------------------------------- --------------- 13
В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В
Введення
В
Для ілюстрацій умов і рішень багатьох завдань люди користуються графіками. За своєю суттю графіки є набором з безлічі точок і відрізків прямих з'єднують ці точки. Виникає питання: чи підкоряються графіки небудь законам і чи мають вони якимись властивостями? Цей питання було поставлено Д. Кенигом, який вперше об'єднав всі схематичні зображення, що складаються з сукупності точок і ліній, загальним терміном "граф" і розглянув граф як самостійний математичний об'єкт. Теорія графів знайшла своє застосування у вирішенні цілого ряду завдань. У моєму курсовому проекті буде розглянуто розділ теорії графів присвячений максимальним повним подграфа, тоесть кліках. Метою проекту є написання програми мовою програмування, яка із заданого графа виділяла б кліку з заданим числом вершин.
Припустимо заданий граф G = (Х, Г). Досить часто виникає завдання пошуку таких підмножин множини вершин Х графа G, які володіють певним, наперед заданим властивістю. Наприклад, яка максимально можлива потужність такого підмножини S ГЌ Х, для якого породжений підграф S є повним? Відповідь на це питання дає Клікова число графа G. Це число і пов'язане з ним підмножина вершин описує важливі струтурние властивості графа і має безпосередні додатки при проведення проектного планування дослідних робіт, у кластерному аналізі та чисельних методах таксономії, паралельних вичмсленіях на ЕОМ, при розміщенні підприємств обслуговування, а також...