Математические заметки Том 101 выпуск 5 май 2017 УДК 519.175.3 Перечисление помеченных геодезических графов с малым цикломатическим числом В.А. Воблый Получены явные формулы для числа помеченных геодезических бициклических, трициклических и тетрациклических графов с заданным числом вершин. <...> Цикломатическим числом связного графа называется увеличенная на единицу разность между числом ребер графа и числом его вершин. k-Циклический граф – это граф с цикломатическим числом, равным k. <...> Точкой сочленения связного графа называется его вершина, после удаления которой вместе с инцидентными ей ребрами граф становится несвязным. <...> Блок – это связный граф без точек сочленения, а также максимальный связный нетривиальный подграф, не имеющий точек сочленения [1; с. <...> Включением вершины степени 2 в ребро (петлю) графа называется его (ее) подразбиение этой вершиной. <...> Обратная операция называется исключением вершины степени 2 из ребра. <...> В результате применения этой операции в графе могут появиться кратные ребра или петля. <...> Два графа называются гомеоморфными, если они могут быть получены друг из друга с помощью последовательности операций включения и исключения вершин степени 2. <...> Гомеоморфным типом называется общий граф (допускаются петли и кратные ребра), не содержащий вершин степени 2, из которого с помощью операций включения вершин степени 2 могут быть получены все графы данного класса гомеоморфных графов [2]. <...> Геодезическим графом называется связный граф, у которого любая пара вершин связана единственной кратчайшей цепью (геодезической). <...> Граф является геодезическим только тогда, когда каждый его блок геодезический граф [3]. <...> Класс графов называется блочно-устойчивым, если из принадлежности графа к этому классу следует принадлежность каждого его блока к этому классу [4]. <...> В.А. Воблый, 2017 c 684 ПЕРЕЧИСЛЕНИЕ ПОМЕЧЕННЫХ ГЕОДЕЗИЧЕСКИХ ГРАФОВ 685 Стемпл и Уоткинс доказали, что граф является геодезическим планарным только тогда <...>