заданими властивостями, встановлення ізоморфізму графів та ін.)

Характеризуючи проблематику теорії графів, можна відзначити, що деякі напрямки носять більш Комбінаторний характер, інші – більш геометричний. До перших відносяться, наприклад, задачі про підрахунок і перерахування графів з фіксованими властивостями, завдання про побудову графів із за даними властивостями Існують напрямки, пов'язані з різними класифікаціями графів, наприклад, за властивостями їх розкладання.

В іншому напрямку досліджень теорії графів вивчаються маршрути, що містять всі вершини або ребра графа. Відомий простий критерій існування маршруту, що містить усі ребра графа: у зв'язкового графі цикл,що містить всі ребра і проходить по кожному ребру один раз, існує тоді і тільки тоді, коли всі вершини графа мають парні ступені. У випадку обходу безлічі вершин графа є тільки ряд достатніх умов існування циклу, що проходить по всіх вершин графа по одному разу.

Характерним специфічним напрямом теорії графів є цикл завдань, пов'язаний з розфарбовуванням графів, в якому вивчаються розбиття множини вершин (ребер), що володіють певними властивостями, наприклад, суміжні вершини (ребра) повинні належати різним множинам (вершини або ребраз одного безлічі фарбують одним кольором).

У теорії графів існують специфічні методи вирішення екстремальних задач. Одна з них заснована на теоремі про максимальний потік і мінімальному розрізі, яка стверджує, що максимальний потік, який можна пропустити через мережу з вершини U в вершину V, дорівнює мінімальній пропускній здатності розрізів, що розділяють вершини U і V. Були побудовані різні ефективні алгоритми знаходження максимального потоку.

Велике значення в теорії графів мають алгоритмічні питання. Для кінцевих графів, тобто для графів з кінцевою безліччю вершин і ребер, як правило, проблема існування алгоритму рішення задач, у тому числі екстремальних, вирішується позитивно. Вирішення багатьох завдань, пов'язаних з