Теория на графите | област от математиката за графите

Различни видове графики

• Теорията на графите има много аспекти. Графите могат да бъдат насочени или неориентирани. Пример за насочен граф е системата от пътища в един град. Някои улици в града са еднопосочни. Това означава, че в тези участъци има само една посока, която може да се следва.
• Графиките могат да бъдат претеглени. Пример за това е пътна мрежа с разстояния или с пътни такси (за пътища).
• Възлите (кръгчетата на схемата) на графа се наричат върхове. Линиите, свързващи върховете, се наричат ръбове. Между два възела може да няма линия, може да има една линия или да има няколко линии.
• В теорията на графите широко се използват структурите на дърветата, които представляват йерархични структури. Дървото е насочен или неориентиран граф, в който няма цикъл, което означава: няма начин да се отиде от един връх (например град) до същия, като се използва всяко ребро, което се използва само веднъж (върви се само веднъж по всеки път, по който се върви).

 
Насочен граф.  

История

→ →

Визуализация на Седемте моста на Кьонигберг. Леонхард Ойлер решава този проблем през 1736 г., което води до развитието на топологията и съвременната теория на графите.

Графът е абстрактна структура от данни. Тя съдържа възли, които обикновено са свързани помежду си. Взел е набор от данни, обикновено под формата на подредени двойки. Възлите са или свързани, или не са свързани с друг възел. Връзката между възлите обикновено се дефинира като Edge (край). Графиките са полезни заради способността им да свързват възли с други възли. В практиката има няколко вида представяне на графи.

Леонхард Ойлер е живял в град, наречен Кьонигсберг. (През 1946 г. името му е променено на Калининград). Градът е разположен на река Прегел. В реката има остров. През реката има няколко моста. Ойлер искал да обиколи и да използва всеки от мостовете по веднъж. Той попитал дали може да направи това. През 1736 г. той публикувал научна статия, в която показал, че това не е възможно. Днес този проблем е известен като "Седемте моста на Кьонигсберг". Статията се разглежда като първата статия в историята на теорията на графите.

Тази статия, както и написаната от Вандермонд статия за проблема с рицаря, продължават анализа на ситус, започнат от Лайбниц. Формулата на Ойлер е за броя на ръбовете, върховете и лицата на изпъкнал полиедър е изучена и обобщена от Коши и Л'Уйе и е в основата на топологията.

Сливането на идеите от математиката с тези от химията е в основата на част от стандартната терминология на теорията на графите. По-специално терминът "граф" е въведен от Силвестър в статия, публикувана през 1878 г. в Nature.

Един от най-известните и продуктивни проблеми на теорията на графите е проблемът за четирите цвята: "Вярно ли е, че всяка карта, начертана в равнината, може да има области, оцветени с четири цвята, по такъв начин, че две области с обща граница да имат различни цветове?"

 
Проблемът с Кьонигсбергския мост на картата на града  


Същият проблем, но с помощта на графика  

Теория на графите в перспектива

Теорията на графите е важна част от математиката и информатиката. За много от тези проблеми съществуват точни решения. В много случаи обаче те са много трудни за изчисляване. Затова много често се използват приближения. Съществуват два вида такива приближения - алгоритми Монте-Карло и алгоритми Лас-Вегас.

 

Свързани страници

• Структура на данните