Графа Обход

граф, на к-ром та или иная числовая характеристика принимает свое минимальное или максимальное значение. Обычно отыскиваются экстремальные значения нек-рой одной числовой характеристики при ограничениях на другие числовые характеристики и свойства. Часто задача состоит в описании множества соответствующих Г. Э. Пусть, напр., зафиксированы целые положительные числа пи kи отыскивается наибольшее число ребер n-вершин-ного графа, не имеющего полных подграфов с вершинами. Установлено, что это число..

- изоморфное отображение графа на себя (см. Графов изоморфизм). Множество всех автоморфизмов данного графа образует группу относительно операции композиции автоморфизмов. Автоморфизмы графа Gпорождают группу подстановок вершин Г(G), наз. Группой (или иногда вершинной группой) графа G, и группу подстановок ребер Г 1(G), наз. Реберной группой графа G. Реберная п вершинная группы графа G без петель и кратных ребер изоморфны тогда и только тогда, когда граф G имеет не более одной изолированной верши..

- приписывание цветов вершинам и (или) ребрам графа, обладающее определенными свойствами. Правильная вершинная (реберная) раскраска - это раскраска вершин (ребер) графа, при к-рой любые смежные вершины (ребра) окрашены в разные цвета. Правильную вершинную раскраску часто наз. Просто раскраской графа. Граф наз. K-pаскрашиваемым, если существует правильная вершинная Г. P. Kцветами. Наименьшее число цветов, достаточное для правильной вершинной раскраски графа G, наз. Хроматическим числом графа G. ..

- одна из топологических характеристик графа. Граф наз. Связным, если для любых его вершин и н vсуществует цепь, соединяющая эти вершины. Числом вершинной связности графа G [обозначение ] наз. Наименьшее число вершин, удаление к-рых (вместе с инцидентными им ребрами) приводит к несвязному графу или к графу, состоящему из одной изолированной вершины. Числом реберной связности [обозначение ] наз. Наименьшее число ребер графа G, удаление к-рых приводит к несвязному графу. Граф G наз. K-связным, е..