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

формула-етилен
Нагледно изобразяване на химичната формула на етилена (С2Н4) чрез графи

Теорията на графите е дял от дискретната математика, който изучава свойствата на графи — схеми, съставени от точки, и отсечките, които ги съединяват. Точките на един граф се наричат негови върхове, а отсечките — ребра. Схемата на улиците на един квартал, където на отсечките са поставени стрелки за посочване посоката на улицата, когато тя е еднопосочна, е пример за ориентиран граф. В теорията на графите два графа, които може да се преобразуват един в друг с непрекъснато деформиране, се смятат за неразличими — такива графи се наричат изоморфни. За начало на теорията на графите се смята една статия на великия швейцарски математик Л. Ойлер (1707 – 1782), в която се решава забавната задача за кьонигсбергските мостове.

кьонигсбергските мостове
Задача за кьонигсбергските мостове: в разположения на двата бряга В и С и на двата острова А и D град Кьонигсбера се търси маршрут, който да минава само по веднъж по всеки от седемте моста а, Ь, с, d. a, f, g (а). Ойлер доказва, че такъв маршрут не съществува, като съпоставя математически модел (0).

Ойлер съпоставя като математичен модел на задачата графа, който я описва — не съществува затворен маршрут по схемата, който да минава само по веднъж по всяко от ребрата на графа, тъй като в противен случай във всеки от върховете на графа би имало толкова влизания, колкото и излизания, т. е. от всеки връх биха излизали по четен брой ребра, което не е вярно. През XX в. започват да изникват задачи, свързани с графи, не само в математиката, но и във физиката, химията, електротехниката, биологията, социологията, икономиката и др. Задача от теорията на графите е знаменитата задача за четирите цвята, поставена през XIX в. Първоначалната й формулировка е следната: може ли всяка от страните на една географска карта да се оцвети в един от дадени четири цвята така, че всеки две съседни страни да са оцветени различно. През 1976 г. американските математици Т. Апел и М. Хейкън съобщават, че са доказали хипотезата за четирите цвята с помощта на компютърна програма.

Вж. Дискретна математика.

Няма коментари - Остави коментар

Вашият коментар

Вашият имейл адрес няма да бъде публикуван. Задължителните полета са отбелязани с *

*

Можете да използвате тези HTML тагове и атрибути: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>