Приложения на теорията на графиките
Плоски графики
Графа G се казва, че е плоска, ако може да бъде представена в равнина по такъв начин, че върховете да са всички отделни точки, краищата са прости криви и никой друг ръб да не се срещат един друг, освен в техните терминали. Например, K 4, пълната графика на четири върха, е плоска, както показва фигура 4А.
За две графики се казва, че са хомеоморфни, ако и двете могат да бъдат получени от една и съща графика от подразделения на ръбовете. Например, графиките на фигура 4А и фигура 4В са хомеоморфни.
Графиката K m, n е графика, за която наборът от върхове може да бъде разделен на две подмножества, едната с m върхове, а другата с n върхове. Всички две върхове на един и същи подмножество не са съседни, докато всички две върхове от различни подмножества са съседни. Полският математик Казимир Куратовски през 1930 г. доказа следната известна теорема:
Необходимо и достатъчно условие графика G да бъде плоска е, че тя не съдържа подграфа хомеоморфна нито на K 5, нито на 3,3, показана на фигура 5.
Един елементарен свиване на графика G е трансформация на G в нов графика G 1, така че два съседни върха ф и ню на G се заменят с нов връх w в G 1 и w е съседен на G 1 за всички върхове на която или u или is е съседна в G. Графа G * се казва, че е свиване на G, ако G * може да се получи от G чрез последователност от елементарни контракции. Следва поредната характеристика на плоска графика, дължима на немския математик К. Вагнер през 1937г.
Графикът е планов, ако и само ако не може да се съкрати до K 5 или K 3,3.
Проблемът с четирицветната карта
Повече от век решението на проблема с четирицветната карта се изплъзваше на всеки анализатор, който се опита. Проблемът може да привлече вниманието на Мебиус, но първата писмена препратка към него изглежда е писмо от един Франсис Гутри до брат му, ученик на Август Де Морган, през 1852 година.
Проблемът се отнася до равнинни карти - тоест подразделения на самолета на необичаеми области, ограничени от прости затворени криви. В географските карти е наблюдавано емпирично, в толкова много специални случаи, колкото са били изпробвани, че най-много четири цвята са необходими, за да се оцветят регионите, така че два региона, които споделят обща граница, да са винаги оцветени по различен начин и в определени случаи, че са необходими поне четири цвята. (Регионите, които се срещат само в даден момент, като щатите Колорадо и Аризона в САЩ, не се считат за обща граница). Една формализация на това емпирично наблюдение представлява това, което се нарича „четирицветна теорема“. Проблемът е да се докаже или опровергае твърдението, че това е така за всяка равнинна карта. Това, че три цвята няма да е достатъчно, е лесно да се докаже, докато достатъчността на пет цвята е доказана през 1890 г. от британския математик PJ Heawood.
През 1879 г. AB Kempe, англичанин, предлага решение на четирицветния проблем. Въпреки че Heawood показа, че аргументът на Kempe е погрешен, две от неговите концепции се оказаха ползотворни при по-късно разследване. Една от тях, наречена неизбежност, правилно заявява невъзможността да се изгради карта, в която всяка от четирите конфигурации отсъства (тези конфигурации се състоят от регион с два съседи, една с три, една с четири и една с пет). Втората концепция, тази на редуцируемостта, получава името си от валидното доказателство на Kempe, че ако има карта, която изисква поне пет цвята и съдържа регион с четири (или три или два) съседи, тогава трябва да има карта, изискваща пет цветове за по-малък брой региони. Опитът на Кемпе да докаже намаляването на карта, съдържаща регион с петима съседи, е погрешен, но той е поправен в доказателство, публикувано през 1976 г. от Кенет Апел и Волфганг Хакен от САЩ. Тяхното доказателство предизвика известна критика, защото наложи оценка на 1936 различни случая, всеки от които включваше 500 000 логически операции. Appel, Haken и техните сътрудници създадоха програми, които дадоха възможност на голям цифров компютър да обработва тези подробности. На компютъра са били необходими повече от 1000 часа за изпълнение на задачата, а полученото официално доказателство е дълго няколкостотин страници.
Ейлерови цикли и проблемът с моста Кьонигсберг
Мултиграф G се състои от непразен набор V (G) от върхове и подмножество E (G) от множеството от непоредни двойки от отделни елементи на V (G) с честота f ≥ 1, прикрепена към всяка двойка. Ако двойката (x 1, x 2) с честота f принадлежи на E (G), тогава върховете x 1 и x 2 се съединяват от f ръбове.
Ейлеровият цикъл на мултиграф G е затворена верига, в която всеки ръб се появява точно веднъж. Ойлер показа, че мултиграфът притежава еулеров цикъл, ако и само ако е свързан (с изключение на изолирани точки) и броят на върховете с нечетна степен е нула или два.
Този проблем първо възникна по следния начин. Река Прегел, образувана от сливането на двата й клона, минава през град Кьонигсберг и тече от двете страни на остров Кнайпхоф. Имаше седем моста, както е показано на Фигура 6А. Гражданите се чудеха дали е възможно да отидат на разходка и да пресекат всеки мост веднъж и веднъж. Това е еквивалентно на намирането на еулеров цикъл за мултиграфа на фигура 6В. Ойлер показа, че е невъзможно, тъй като има четири върха с нечетен ред.
