Графов Изоморфизм

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

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

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

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