WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Основні поняття теорії графів - Реферат

Основні поняття теорії графів - Реферат

ідентифікують їхнівершини, або нумерують вершини натуральними числами.
Ізоморфне відображення графа G на себе називається автоморфізмом графа G. Автоморфізм графа G =(V,E ), при якому для кожної вершини v V виконується (v)=v, називається тривіальним автоморфізмом.
Приклад 3.6. Пропонуємо переконатись, що всі графи, зображені на рис.3.2, ізоморфні між собою, а графи на рис.3.3 не є ізоморфними.
G1 G2 G3
Рис.3.2
H1 H2
Рис.3.3
Відношення ізоморфізму є відношенням еквівалентності на сукупності графів.
Теорема 3.1. Графи G1 та G2 ізоморфні тоді і тільки тоді, коли матрицю суміжності (матрицю інцидентності) одного з цих графів можна одержати з матриці суміжності (матриці інцидентності) іншого графа за допомогою відповідних перестановок рядків та стовпчиків.
Доведення. Справді, як було зазначено вище, ізоморфні графи G1 і G2 відрізняються між собою лише порядком нумерації вершин, тобто існує бієктивне відображення множини номерів вершин першого графа на множину номерів вершин другого. Отже, кожен елемент aij(1) матриці суміжності A1 графа G1 збігається з елементом a (i) (j)(2) (тобто елементом, який знаходиться в рядку з номером (i ) і стовпчику з номером (j)) матриці суміжності A2 графа G2. Таким чином, шляхом послідовного одночасного обміну місцями (перестановок) рядків і стовпчиків з номерами i та (i ) для всіх i=1,2,...,n матрицю суміжності A1 можна перетворити у матрицю суміжності A2 і навпаки.
Якщо відображення відоме, то таке перетворення виконати неважко. У разі ж, коли потрібно перевірити за допомогою матриць суміжності, чи є ізоморфними два задані графи з n вершинами кожний, необхідно здійснити різноманітні одночасні перестановки рядків і стовпчиків однієї з них. Якщо після чергової з таких перестановок дістанемо матрицю, яка повністю збігається з іншою, то ці графи ізоморфні. Однак, щоб в такий спосіб з'ясувати, що задані графи не є ізоморфними, потрібно виконати всі n! перестановок рядків і стовпчиків. Вже для порівняно невеликих значень n здійснити цей перебір практично неможливо навіть за допомогою обчислювальної машини. У прикладній теорії алгоритмів розробляються різноманітні алгоритми перевірки ізоморфізму графів, які для більшості графів (або окремих типів графів) дозволяють суттєво скоротити обсяг необхідних перевірок [2,7,8].
Для матриць інцидентності графів G1 і G2 з n вершинами і m ребрами кожний справедливі аналогічні міркування. Відмінність у тому, що коли G1 і G2 ізоморфні, тоді для їхніх множин вершин існує бієкція , а для множин ребер інша бієкція . Загальна ж кількість необхідних кроків для перевірки ізоморфізму графів G1 і G2 у цьому випадку не перевищує n!m!.
Граф G =(V,E ) називається повним, якщо будь-які дві його вершини суміжні (тобто E=V (2)). Повний граф з n вершинами позначається Kn.
Очевидно, що будь-яка підстановка множини вершин повного графа Kn є автоморфізмом цього графа. Тому кількість усіх можливих автоморфізмів графа Kn дорівнює n!
Для графів можна означити операції об'єднання, перетину і доповнення.
Об'єднанням графів G1=(V1,E1) і G2=(V2,E2) називається граф G =(V1 V2,E1 E2); позначається G =G1 G2. Об'єднання G =G1 G2 називається прямою сумою графів G1 i G2, якщо V1 V2= .
Перетином і різницею графів G1=(V,E1) i G2=(V,E2) з однаковими множинами вершин називаються графи G =(V,E1 E2) i G =(V,E1E2) відповідно; позначаються G =G1 G2 і G = G1G2.
Доповненням графа G =(V,E ) називається граф =(V,V (2)E ). Отже, граф має ту саму множину вершин V, що і граф G, а вершини графа суміжні тоді і лише тоді, коли вони несуміжні в G. Для графа G з n вершинами виконується =KnG.
Таким чином можна означити алгебру графів A= (типу (2,2,1)), носієм якої є множина Г всіх графів. Iснують й інші операції для графів, отже, сигнатуру алгебри A можна розширювати.
Неважко переконатись у справедливості такого твердження.
Теорема 3.2. Графи G1 i G2 ізоморфні тоді і тільки тоді, коли ізоморфні їхні доповнення 1 i 2.
Приклад 3.7. Об'єднання і перетин графів H1 і H2 з попереднього прикладу зображені на рис.3.4. Доповнення графів G2 i H2 зображені на рис.3.5.
H1 H2 H1 H2
Рис.3.4
2 2
Рис.3.5
Граф як модель. Застосування теорії графів
Останнім часом графи і пов'язані з ними методи досліджень використовуються практично в усіх розділах сучасної математики і, зокрема, дискретної математики.
Граф є математичною моделлю найрізноманітніших об'єктів, явищ і процесів, що досліджуються і використовуються в науці, техніці та на практиці. Коротко опишемо найвідоміші застосування теорії графів.
Наприклад, у вигляді графа можуть бути зображені:
електричні і транспортні мережі;
інформаційні і комп'ютерні мережі;
карти автомобільних, залізничних і повітряних шляхів, газо- і нафтопроводів;
моделі кристалів;
структури молекул хімічних речовин;
моделі ігор;
різні математичні об'єкти (відношення, частково впорядковані множини, решітки, автомати, ланцюги Маркова, алгоритми і програми тощо);
лабіринти;
плани діяльності або плани виконання певних робіт (розклади);
генеалогічні дерева тощо.
Приклади застосування теорії графів:
пошук зв'язних компонентів у комунікаційних мережах;
пошук найкоротших, "найдешевших" та "найдорожчих" шляхів у комунікаційних мережах;
побудова кістякового дерева: зв'язність з найменшою можливою кількістю ребер;
пошук максимальної течії для транспортної мережі, в якій визначено вхідні та вихідні вершини та пропускні спроможності ребер;
ізоморфізм графів: ідентичність структур молекул (ізометрія);
знаходження циклів графів:
гамільтонів цикл: обійти всі вершини графа, побувавши в кожній з них лише один раз (задача комівояжера);
ейлерів цикл: обійти всі ребра (контроль дієздатності мережі);
розфарбування графів: розфарбування географічних карт, укладання розкладів, розміщення ресурсів тощо;
планарність графів: проектування друкованих електронних та електричних схем, транспортних розв'язок тощо;
знаходження центрів графа: вершин, максимальна відстань від яких до всіх інших вершин графа є мінімальною ("столиць")
тощо.
Список використаної літератури
1. Харари Т. Теория графов.- М.,1973.
2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И.- М., 1990.
3. Зыков А.А. Основы теории графов.- М., 1987.
4. Оре О. Теория графов.- М., 1980.
5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.
6. Уилсон Р. Введение в теорию графов.- М., 1977
7. Кристофидес Н. Теория графов. Алгоритмический подход.- М.,1978
8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. - М.,1980
Loading...

 
 

Цікаве