Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Теорія графів



План:


Введення

Граф з шістьма вершинами та сімома ребрами

Теорія графів - розділ дискретної математики, що вивчає властивості графів. У загальному значенні граф представляється як безліч вершин (вузлів), з'єднаних ребрами. У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якого рахункового множини, а E - підмножина V V.

Теорія графів знаходить застосування, наприклад, в геоінформаційних системах (ГІС). Існуючі або запроектовані будинки, споруди, квартали і т. п. розглядаються як вершини, а з'єднують їхні дороги, інженерні мережі, лінії електропередачі і т. п. - як ребра. Застосування різних обчислень, вироблених на такому графі, дозволяє, наприклад, знайти найкоротший об'їзний шлях або найближчий продуктовий магазин, спланувати оптимальний маршрут.

Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез.


1. Історія виникнення теорії графів

Родоначальником теорії графів вважається Леонард Ейлер. У 1736 році в одному зі своїх листів він формулює і пропонує рішення завдання про сім Кенигсбергских мостах, що стала згодом однією з класичних задач теорії графів.

2. Термінологія теорії графів

Термінологія теорії графів понині не визначена суворо. Зокрема в монографії Гудман, Хідетніемі, 1981 сказано: "У програмістської світі немає єдиної думки про те, який з двох термінів" граф "або" мережа ". Ми вибрали термін "мережа", так як він, мабуть, частіше зустрічається у прикладних областях ". Аналогічна ситуація для" вершина / точка "


3. Зображення графів на площині

При зображенні графів найчастіше використовується наступна система позначень: кожній вершині зіставляється точка на площині, і якщо між вершинами існує ребро, то відповідні точки з'єднуються відрізком. У разі орієнтованого графа відрізки замінюють стрілками.

Не слід плутати зображення графа із власне графом (абстрактної структурою), оскільки одному графу можна зіставити не одне графічне представлення. Зображення покликане лише показати, які пари вершин з'єднані ребрами, а які - ні. Часто на практиці буває важко відповісти на питання, чи є два зображення моделями одного і того ж графа чи ні. Залежно від завдання, одні зображення можуть давати більш наочну картину, ніж інші.


4. Деякі задачі теорії графів

До теорії графів також відноситься цілий ряд математичних проблем, не вирішених на сьогоднішній день.


5. Застосування теорії графів


Література

  • Хімічні програми топології і теорії графів. Під ред. Р. Кінга. Пер. з англ. М.: Мир, 1987.
  • Кірсанов М. Н. Графи в Maple. М.: Физматлит, 2007. 168

Примітки

  1. Г. С. Яблонський, В. І. Биков, А. Н. Горбань, Кінетичні моделі каталітичних реакцій - thermotree.narod.ru/contybg1983.htm, Новосибірськ: Наука (Сіб. відділення), 1983 .- 255 c.
  2. Курейчик В. М., Глушань В. М., Щербаков Л. І. Комбінаторні апаратні моделі та алгоритми в САПР. М.: Радіо і зв'язок, 1990. 216 с.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Дерево (теорія графів)
Шлях (теорія графів)
Клітка (теорія графів)
Кліка (теорія графів)
Петля (теорія графів)
Шарнір (теорія графів)
Зв'язність графів
Ізоморфізм графів
Візуалізація графів
© Усі права захищені
написати до нас
Рейтинг@Mail.ru