График

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

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

отношение между двумя конструктивными объектами, заключающееся в том, что эти объекты одинаковым образом составлены из одинаковых элементарных знаков. Г. Р. Двух слов означает, что они составлены из одних и тех же букв, одинаково следующих друг за другом. Точнее Г. Р. Слов можно охарактеризовать следующим образом. А) пустое слово считается графически равным только самому себе. Б) два непустых слова и (здесь и означают последние буквы этих слов) считаются графически равными тогда и только ..

отношение эквивалентности на множестве графов, характеризующее их геометрия, свойства. Г. Г. Определяется следуюпшм образом. Подразбиением ребра ( а, b).графа Gназ. Операция, состоящая в добавлении новой вершины v, удалении ребра (а, b).и добавлении двух ребер (a, v).и (b, v). Геометрически эта операция состоит в выделении на линии (a, b).нек-рой (внутренней) точки v, к-рая объявляется новой вершиной. Граф G' наз. Подразбиением графа G, если он может быть получен из G путем применения нек-рого ..