Qraf nəzəriyyəsi

Altı zirvəli və yeddi kənarı olan qraf

Qraf nəzəriyyəsi — qrafların xüsusiyyətlərini öyrənən diskret riyaziyyatın bir qolu. Ümumi mənada bir qrafik kənarları ilə birləşdirilmiş zirvələr (düyünlər) toplusu kimi təmsil olunur. Qəti tərifdə qraf $G=(V,E)$ cüt cütüdür, burada $V$ istənilən sayılan çoxluğun alt dəstidir və $E$ — altdır $V\times V$.

Qraf nəzəriyyəsi, məsələn, coğrafi informasiya sistemlərində (CİS) istifadə olunur. Mövcud və ya yeni dizayn edilmiş evlər, tikililər, məhəllələr və s. zirvələr, onları birləşdirən yollar, mühəndis şəbəkələri, elektrik xətləri və s. Belə bir qrafik üzərində aparılmış müxtəlif hesablamaların istifadəsi, məsələn, ən qısa yol yolunu və ya ən yaxın ərzaq mağazasını tapmaq və optimal marşrutu planlaşdırma imkanı verir.

Qraf nəzəriyyəsi çox sayda həll olunmamış problemi və hələ təsdiqlənməmiş fərziyyələri ehtiva edir.

Qraf nəzəriyyəsinin tarixi

Qraf nəzəriyyəsinin banisi Leonard Eyler. 1736-cı ildə məktublarından birində, daha sonra qraf nəzəriyyəsində klassik problemlərdən biri halına gələn yeddi Koenigsberg körpüsü problemini həll edir və həll təklif edir. "Sayı" ifadəsi ilk dəfə Silvester, Ceyms Yozef tərəfindən 1878-ci ildə Nature jurnalında yayımlanan məqaləsində gətirilmişdir.

Qraf nəzəriyyəsinin terminologiyası

Qraf nəzəriyyəsinin terminologiyası hələ də ciddi şəkildə müəyyənləşdirilməyib. Xüsusən, Goodman, Hidetniemi, 1981-ci ildə çap edilən monoqrafiyasında deyilir: "Proqram dünyasında iki termindən hansının" qraf "və ya" şəbəkə "olduğuna dair dəqiq fikir birliyi yoxdur. Tətbiq sahələrində daha çox göründüyü üçün "şəbəkə" ifadəsini seçdik. " Vəziyyət "top / point" ifadələri ilə eynidir.

Qrafların növləri:

• yönləndirilməmiş
• yönləndirilmiş

Ədəbiyyat

• Дистель Р. Теория графов Пер. с англ. - Новосибирск: Издательство института математики, 2002. - 336 с. ISBN 5-86134-101-X.
• Diestel R. Graph Theory, Electronic Edition. NY: Springer-Verlag. 2005. 422.
• Басакер Р., Саати Т. Конечные графы и сети = Finite Graphs and Networks. — М.: Наука, 1974. — 368 c.
• Белов В. В., Воробьёв Е. М., Шаталов В. Е. Теория графов. М.: Высш. школа. 1976. 392.
• Берж К. Теория графов и её приложения. М.: ИЛ, 1962. 320c.
• Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
• Зыков, Александр Александрович. Основы теории графов. М.: Вузовская книга. 2004. 664. ISBN 5-9502-0057-8.(М.: Наука, 1987. 383c.)
• Химические приложения топологии и теории графов. Под ред. Р. Кинга. Пер. с англ. М.: Мир, 1987.
• Кирсанов М. Н. Графы в Maple. М.: Физматлит, 2007. 168 c. http://vuz.exponenta.ru/PDF/book/GrMaple.pdf http://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
• Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978. 429c.
• Кормен Т. Х. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ (2-е изд). М.: Вильямс. 2006 [Introduction to Algorithms]. 1296. ISBN 0-07-013151-1.
• Оре О. Теория графов (2-е изд). М.: Наука. 1980. 336.
• Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. М.: Физико-математическая литература. 1997. ISBN 5-02-015033-9.
• Свами М., Тхуласираман К. Графы, сети и алгоритмы. М: Мир, 1984. 455с.
• Татт У. Теория графов. Пер. с англ. М.: Мир, 1988. 424 с. Arxivləşdirilib 2020-08-03 at the Wayback Machine
• Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с.
• Харари Ф. Теория графов. М.: Мир. 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
• Харари Ф., Палмер Э. Перечисление графов. Мир. 1977.
• Сергей Мельников. Сим и Крэм под "электронным микроскопом" (Наука и жизнь). 1996. 144–145. В статье идёт речь об игре на графе Сим, придуманной Густавом Симмонсом.

Xarici keçidlər

• WikiGrapp — qraf nəzəriyyəsinin izahlı lüğəti
• alqoritmləri və qısa C təsvirləri
• Ayrı-ayrı riyaziyyat, alqoritmlər, kiçiklər, qrafik görselleştirme
• [www.xumuk.ru/encyklopedia/1148.html Kimiyada qraflar]
• Intelligent Graph Visualizer (təyyarədə avtomatik yerləşdirmə, ən qısa yolu tapmaq, mərkəz tapmaq və s.)
• Graph Theory Software Arxivləşdirilib 2013-03-13 at the Wayback Machine
• Visual Graph: istifadəçiyə qrafiklərdə məlumatları vizuallaşdırmaq və axtarmaq üçün geniş vasitə və metodlar təqdim edən bir proqram