Теория на графите

Теорията на графите е клон от математиката, който изучава свойствата на графите.

Фиг. 1
Фиг. 2

Графът е абстрактна структура, която представя връзките между отделните елементи на дадено множество. Всеки член на това множество се нарича връх, а връзката между два върха се нарича ребро. Наименованията връх и ребро идват от най-често използваното визуално представяне на графа, както е показано на фиг. 1. Върховете са оцветени в черно, а ребрата – в зелено.

История

Първата работа по теория на графите е статията на Ойлер за Кьонигсбергските мостове (1736). Тя обаче остава единствена в течение на 100 години. Интересът към този клон от математиката и към частния случай – дърветата, се възражда около средата на 19 век и е съсредоточен главно в Англия. Върху развитието на Теорията на графите оказват забележимо влияние естествените науки, тъй като тя има приложения в различни области – при изследването на електрическите вериги, моделите на кристалите, структурата на молекулите, в теорията на игрите и програмирането, в биологията и психологията и т.н.

Терминът е употребен най-напред в статия на Кьониг, а след това и в монографията му „Theorie der endlichen und unendlichen Graphen“ („Теория на крайните и безкрайните графи“, 1936), но самият Кьониг го е заимствал от статия на Шур (1912), в която граф се нарича фигура, състояща се от няколко числа или точки, някои двойки от които са съединени помежду си.

други езици
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
čeština: Teorie grafů
dansk: Grafteori
Ελληνικά: Θεωρία γράφων
English: Graph theory
Esperanto: Grafeteorio
euskara: Grafo teoria
Bahasa Indonesia: Teori graf
íslenska: Netafræði
日本語: グラフ理論
한국어: 그래프 이론
lietuvių: Grafų teorija
latviešu: Grafu teorija
монгол: Графын онол
Bahasa Melayu: Teori graf
Nederlands: Grafentheorie
norsk nynorsk: Grafteori
norsk: Grafteori
português: Teoria dos grafos
sicilianu: Tiuria dî grafi
srpskohrvatski / српскохрватски: Teorija grafova
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
svenska: Grafteori
Türkçe: Çizge teorisi
українська: Теорія графів
Tiếng Việt: Lý thuyết đồ thị
吴语: 图论
中文: 图论
粵語: 圖論