Geum.ru

Основи теорії графів. Властивості ойлерових та гамільтонових графів

Курсовой проект - Математика и статистика

Другие курсовые по предмету Математика и статистика

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

Наприклад, у вигляді графа можуть бути зображені:

електричні і транспортні мережі;

інформаційні і компютерні мережі;

карти автомобільних, залізничних і повітряних шляхів, газо- і нафтопроводів;

моделі кристалів;

структури молекул хімічних речовин;

моделі ігор;

різні математичні обєкти (відношення, частково впорядковані множини, решітки, автомати, ланцюги Маркова, алгоритми і програми тощо);

лабіринти;

плани діяльності або плани виконання певних робіт (розклади);

генеалогічні дерева тощо.

Приклади застосування теорії графів:

пошук звязних компонентів у комунікаційних мережах;

пошук найкоротших, “найдешевших” та “найдорожчих” шляхів у комунікаційних мережах;

побудова кістякового дерева: звязність з найменшою можливою кількістю ребер;

пошук максимальної течії для транспортної мережі, в якій визначено вхідні та вихідні вершини та пропускні спроможності ребер;

ізоморфізм графів: ідентичність структур молекул (ізометрія);

знаходження циклів графів:

гамільтонів цикл: обійти всі вершини графа, побувавши в кожній з них лише один раз (задача комівояжера);

ейлерів цикл: обійти всі ребра (контроль дієздатності мережі);

розфарбування графів: розфарбування географічних карт, укладання розкладів, розміщення ресурсів тощо;

планарність графів: проектування друкованих електронних та електричних схем, транспортних розвязок тощо;

знаходження центрів графа: вершин, максимальна відстань від яких до всіх інших вершин графа є мінімальною (“столиць”).

 

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

 

  1. Белов В.В. и др. Теория графов:учебное пособие для втузов.- М.: „Высшая школа”,1976. 392 с.
  2. Березина Л.Ю. Графы и их применение. М.: Просвещение, 1979. 143 с.
  3. Гервер М. Трехзначные числа и орграфы // Журнал Квант, Москва, МЦНМО, 1987, №2

4.Кузнецов О.П. Дискретная математика для инженеров. / О.П. Кузнецов, Г.М. АдельсонВельский 2е изд., перераб. и доп. М.: Энергоатомиздат, 1988 400 с.: ил.

5.Мелихов А.Н. применение графов для проектирования дискретных устройств. / А.Н. Мелихов, Л.С. Бернштейн, В.М. Курейчик М.: Наука, 1974. 304 с.: ил.

  1. Уилсон Р. Введение в теорію графов. М.: Мир, 1777. 208 с.
  2. Оре О. Графы и их применение. М.: Изд-во „Мир”, 1965.- 174 с.
  3. Оре О. Теория графов. 2-е изд.- М.: „Наука”, 1980.- 205 с.
  4. Уилсон Р. Введение в теорію графов. М.: Мир, 1777. 208 с.
  5. Хаггарти Р Дискретная математика для программистов. М.: Техносфера, 2003. 320 с.
  6. Ядренко М.Й. Дискретна математика : навчальний посібник. К.: Вид. поліграф.центр „Експрес”, 2003. 244 с.