Теория графов и навигация

Список публикаций. Часть Q-S

Список публикаций. Часть M-P

Список публикаций. Часть E-L

Нам показалось интересным опубликовать список публикаций этого автора.

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

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин. Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра.

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

Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл.

Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.