Родоначальником теории графов принято считать знаменитого теоретика и математика Леонарда Эйлера (1707-1783), родившегося в Швейцарии. Историю возникновения этой теории можно проследить по переписке великого ученого к авторитетному инженеру Мариони, с которым Эйлер вел переписку по самым разным вопросам науки и техники.

Семь мостов Кёнигсберга, или Задача о семи кёнигсбергских мостах — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году математиком Леонардом Эйлером, доказавшим, что это невозможно, и изобретшим таким образом эйлеровы циклы.

Дерево – это связный ациклический граф. Связность означает наличие путей между любой парой вершин ацикличность – отсутствие циклов и то, что между парами вершин имеется только по одному пути. Название «дерево» выбрано не случайно, потому что очевидно некоторое внешнее сходство с деревом-растением.

Ориентированный граф (орграф) – граф, ребрам которого присвоено направление.

Неориентированный граф – множество как угодно размещенных на плоскости, точек, некоторые из которых соединены линиями любой формы. Два неориентированных графа считаются неразличимыми, если они отличаются друг от друга только формой соединительных линий или способом размещения точек на плоскости.

Смешанный граф – это граф, в котором некоторые ребра могут быть ориентированными, а некоторые – неориентированными.
Ориентированный и неориентированный граф ориентированными, а некоторые – неориентированными являются частными случаями смешанного.

Эйлеров граф – граф, содержащий эйлеров цикл, проходящий через каждое ребро (дугу) графа ровно по одному разу.

Взвешенный граф (орграф) – это граф (или орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа-пометки могут быть различными: вес, длина, стоимость.

Мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных ребер (их также называют «параллельными), то есть ребра, имеющие те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром.

Полуэйлеров граф – граф, содержащий эйлеров путь (цепь), проходящий по всем дугам (ребам) графа и притом только по одному разу.

Гамильтонов граф - содержит гамильтонов цикл, замкнутый путь, который содержит все вершины (точки) данного графа.

Полный граф – когда две его различные вершины соединены одним и только одним ребром (в отличие от мультиграфа). В полном графе каждая его вершина принадлежит одному и тому же числу ребер. Для задания его графа достаточно знать число его вершин.

Нулевой граф - граф, состоящий из «изолированных» вершин, без ребер.

При строительстве новых кварталов, домов их принимают за вершины графа, а коммуникации – дороги, линии электропередач, водопровод, тепловые сети, канализационные – это ребра и дуги. Применение специальных методов на таком графе позволяет найти кратчайший объездной путь, а также помогает спланировать более удобный и оптимальный маршрут. При помощи графа производится поиск оптимальных путей прокладки коммуникаций.

Переливание крови – важный вопрос в современной медицине. Всего существует четыре группы крови. При переливании крови от одного человека к другому не все группы совместимы. С помощью графа можно наглядно показать возможные варианты переливания крови. Групп крови – это вершины графа с соответствующими номерами, а стрелки указывают на возможность переливания одной групп крови человеку с другой группой крови. Например, кровь первой групп крови можно переливать любому человеку, а человек с первой группой крови воспринимает только кровь своей группы.

Деревья играют большую роль в биологической теории ветвящихся процессов. Самый простой пример – размножение. Бактерии размножаются путем деления с очень высокой скоростью. В среднем за 20-30 минут из одной бактерии появляются 2-е новые!

Компьютерная химия (хеминформатика и биоинфоматика) – сравнительномолодая область химии и биолигии. Их основой является теория графов и комбинаторики. На стыке трех наук – химии, биологии, информатики, - решаются проблемы, для которых раньше необходимы были годы исследований, тысячи подопытных животных и добровольцев, испытывавших на себе новые синтетические лекарственные средства. Сейчас эти дорогостоящие процедуры решают с помощью различных программ и онлайн-сервисов.

Одной из самых сложных и утомительных задач радиотехники было конструирование печатных схем.
Печатная схема – пластинка из изолирующего материала, на которой в виде металлических полосок выставлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи. Решение этой задачи упростилось благодаря теории графов. В ходе решения этой задачи необходимо вчертить плоский граф. С вершинами в указанных точках. А благодаря теории графов эта задача теперь формализована, и расчет дорожек производит компьютер.

Нам часто приходится обращаться к навигационным сайтам. Навигационная структура (карта) сайта дает представление о взаимосвязях всех страниц сайта. Ее можно представить в виде ориентированного графа.