Курсовий проект студента Шеломанова Р.Б.
Кафедра загальної теорії систем і системного аналізу
Московський державний університет економіки, статистики та інформатики
Москва 1998
Введення
Для ілюстрацій умов і рішень багатьох завдань люди користуються графіками. За своєю суттю графіки є набором з безлічі точок і відрізків прямих з'єднують ці точки. Виникає питання: чи підкоряються графіки небудь законам і чи мають вони якимись властивостями? Це питання було поставлено Д. Кенігом, який вперше об'єднав всі схематичні зображення, що складаються із сукупності точок і ліній, загальним терміном "граф" і розглянув граф як самостійний математичний об'єкт. Теорія графів знайшла своє застосування в вирішенні цілого ряду завдань. У моєму курсовому проекті буде розглянуто розділ теорії графів присвячений максимальним повним підграф, тоесть кліках. Метою проекту є написання програми на мові програмування, яка із заданого графа виділяла б кліку з заданим числом вершин.
Припустимо заданий граф G = (Х, Г). Досить часто виникає завдання пошуку таких підмножин множини вершин Х графа G, які володіють певним, наперед заданою властивістю. Наприклад, яка максимально можлива потужність такого підмножини S ГЌ Х, для якого породжений підграф S є повним? Відповідь на це питання дає Клікова число графа G. Це число і пов'язане з ним підмножина вершин описує важливі струтурние властивості графа і має безпосередні докладання при проведення проектного планування дослідних робіт, в кластерному аналізі та чисельних методах таксономії, паралельних вичмсленіях на ЕОМ, при розміщенні підприємств обслуговування, а також джерел і споживачів у енергосистемах.
Частина 1. Теоретична частину до курсового проекту
Глава1. Теорія графів
Поняття графа
Графом G (X, U) називається сукупність двох об'єктів деякого безлічі X і відображення цієї множини в себе Г .
-->>
При геометричному поданні графа елементи безлічі Х зображуються точками площини і називаються вершинами графа. Лінії, що з'єднують будь-які пари точок x і y , з яких у є відображенням х , називаються дугами графа. Дуги графа мають напрямок, позначуване стрілкою, яка спрямована вістрям від елемента х до його відображенню у .
Вершини і лінії графа
Дві вершини А і В є граничними вершинами дуги, якщо А - початок дуги, а В її кінець.
Суміжними називаються різні дуги, що мають загальну граничну точку. Дві вершини х і у суміжні, якщо вони різні і існує дуга, що йде від однієї з них до іншої.
Вершина називається ізольованою, якщо вона не з'єднана дугами з іншими вершинами графа.
Якщо дуга U виходить з вершини х або заходить в х , то дуга U називається інцидентності вершині х , а вершини х інцидентності дузі U . Загальне число дуг, інцидентних вершині х , є ступенем вершини х Р (х) . Вершини, ступінь яких Р (х)> 2 , називаються вузлом, а зі ступенем Р (х) <2 - антіузлом.
Полустепень заходу Р + (х) вершини х - Кількість дуг, що заходять в дану вершину. Полустепень результату Р-(х) - кількість дуг, що виходять з цієї вершини.
Послідовність ліній на графі
Шлях - послідовність дуг ( U1, U2, ... Un ), в якій кінець кожної попередньої дуги збігається з початком наступної. Шлях може бути кінцевим і нескінченним.
Шлях називається простим, якщо в ньому ніяка дуга не зустрічається двічі, і складовим, якщо будь-яка з дуг зустрічається більше одного рази.
Шлях, в якому жодна з вершин не зустрічається більше одного разу, називається елементарним шляхом.
Гамільтоном шлях - шлях проходить через усі вершини, але тільки по одному разу,
Еллер шлях - шлях містить всі дуги графа, при цьому тільки по одному разу.
Довжина шляху - число дуг послідовності ( U1, U2, ... Un ).
Гілка - шлях, в якому початкова та кінцева вершини є вузлами. Дуга (x, y) називається замикаючої, якщо видалення її не призводить до анулювання шляху з x в y.
Контур - кінцевий шлях, що починається і закінчується в одній і тій же вершині. Контур одиничної довжини називається петлею.
Орієнтований граф - граф, у якого вершини з'єднуються напрямними стрілками.
Графи можна розглядати з урахуванням або без урахування орієнтації його дуг.
Різновиди графів
Нуль-граф - граф (X, U) , що складається тільки з ізольованих вершин.
Однорідний граф - якщо ступеня всіх вершин графа однакові і P + (x) = P-(x) = 0.
симетричних граф - граф, в якому дві будь-які суміжні вершини з'єднані тільки двома протилежно орієнтованими дугами.
Антісімметріческій - граф, в якому кожна пара суміжних вершин з'єднана тільки в одному напрямку.
Повний - граф, в якому будь-яка пара вершин з'єднана однаковим числом дуг.
мультіграф - граф, в якому хоча б дві суміжні вершини з'єднані більш ніж однією дугою. Найбільше число дуг, що з'єднують суміжні вершини графа називається кратністю.
Підмножини графів
підграф графа G (X, U) називається граф G (A, UA) , який визначається наступним чином:
1. Вершинами A подграфа G (A, UA) є деяку підмножину вершин графа G (X, U);
2. Відображенням кожної вершини подграфа є перетин відображення тієї ж вершини в графі G (X, U) з усім підмножиною вершин A подграфа G (A, UA).
Частковим графом для графа G (X, U) називається граф G (X, U) , в якому містяться всі вершини і деяку підмножину дуг вихідного графа.
Частковий підграф - це частковий граф від подграфа.
Фактором графа G (X, U) називається частковий граф G (X, U) , в якому кожна вершина володіє полустепенямі результату і заходу, рівними одиниці, є одна заходящая і одна витікаюча дуги.
Базисним графом називається орієнтований частковий граф, утворений з вихідного видаленням петель і замикаючих дуг.
Зв'язність графа
У загальному випадку граф може бути представлений декількома окремими графами, не мають загальних дуг. Тоді граф G (X, U) називається незв'язних, а кожен з складових його графів G1, G2 , ... Gn - компонентами зв'язності. Граф називається зв'язковим, коли кожну його вершину можна з'єднати з будь-якої іншої його вершиною деякої ланцюгом.
Операції над графами
1. Об'єднання графів
G3 (X3, Гх3) = G1 (X1, Г1х1) Г€ G2 (X2, Г2х2) , де X3 = X1 Г€ X2, а Гx3 = Г1x1 Г€ Г2x2
Приклад (Рис 1.1).
Рис 1.1
2. Перетин графів
G3 (X3, Гх3) = G1 (X1, Г1х1) Г‡ G2 (X2, Г2х2) , де X3 = X1 Г‡ X2, а Гx 3 = Г1x1 Г‡ Г2x2
Приклад (рис 1.2).
Рис 1.2
4. Пряме (декартовій) твір графів.
Прямим твором множин Х {x1 ....... xn} і Y називається безліч Z, елементами якого є всілякі пари виду xi, yj , Де xiГЋX, yjГЋY. Позначають: Z = X x Y.
G3 (X3, Гх3) = G1 (X1, Г1х1) Г‡ G2 (X2, Г2х2) , де X3 = X1 Г‡ X2, а Гx3 = Г1х1 Г‡ Г2х2
Приклад. (Рис 2.3)
G1 (X, Гх) = G1 (X1, Гх1) G2 (Y, Гy) = G2 (X2, Гх2)
X = {x1 x2 x3} Y = {y1 y2}
Гх1 = 0 Гу1 = {y1 y1}
Гх2 = {x1 x3} Гу2 = {y1}
Гх3 = 0
Z = X x Y = {x 1 y1, x1y2, x2y1, x2y2, x3y1, x3...
