Частотный раздел графика
В теории графов , дисциплине внутри математики , частотное разбиение графа ( простой граф ) — это разбиение его вершин , сгруппированных по их степени. Например, последовательность степеней левого графа ниже (3, 3, 3, 2, 2, 1), а его частотное разбиение равно 6 = 3 + 2 + 1. Это означает, что он имеет 3 вершины с некоторой степенью , 2 вершины с другой степенью и 1 вершина с третьей степенью. Последовательность степеней двудольного графав середине ниже (3, 2, 2, 2, 2, 2, 1, 1, 1), а его частотное разбиение равно 9 = 5 + 3 + 1. Последовательность степеней правого графика ниже (3 , 3, 3, 3, 3, 3, 2), а его частотное разбиение равно 7 = 6 + 1.
В общем случае существует множество неизоморфных графов с заданным частотным разбиением. Граф и его дополнение имеют одно и то же частотное разбиение. Для любого разбиения p = f 1 + f 2 + ... + f k целого числа p > 1, отличного от p = 1 + 1 + 1 + ... + 1, существует хотя бы один (связный) простой граф имея этот раздел в качестве своего частотного раздела. [1]
Частотные разбиения различных семейств графов полностью идентифицируются; частотные разбиения многих семейств графов не выявлены.
Для частотного разбиения p = f 1 + f 2 + ... + f k целого числа p > 1 его последовательность графических степеней обозначается как ((d 1 ) f 1 ,(d 2 ) f 2 , (d 3 ) f 3 , ..., (d k ) f k ), где степени d i различны и f i ≥ f j для i < j . Бхат-наяки другие. (1979) показали, что разбиение p на k частей, k ≤ целой части , является частотным разбиением [2] эйлерова графа и наоборот.
Частотные разбиения семейств графов, таких как деревья [3] , гамильтоновы графы [4] , ориентированные графы и турниры [5] и k-однородные гиперграфы . [6] были охарактеризованы.