Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

О СПОСОБАХ ПОСТРОЕНИЯ РЕГУЛЯРНЫХ ГРАФОВ

Белаш А.Н. 1
1 Северо-Кавказский федеральный университет
1. Цветкович Д.М., Дуб М., Сачс Х. Спектр графов: теория и применение. – 3-е изд. – Нью-Йорк: Уайли, 1998.

При построении регулярных графов необходимо учитывать то, что они могут быть получены из полных графов.

В задачах компьютерного моделирования и составления различного рода структур данных часто необходимо работать с регулярными графами.

Регулярный граф – граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается r(G) .

На сегодняшний день известны следующие способы построения регулярных графов:

1) матрица смежности;

2) матрица инцидентности;

3) случайный граф;

Полный граф Km является сильно регулярным для любого m.

Построение регулярного графа со степенью n представляет собой сложность, если строить его начиная с нуль-графа или с одной вершины. Чтобы построить регулярный граф со степенью r(G) < n, необходимо вначале построить полный граф со степенью n и далее равномерно удалить из него «лишние» ребра. Такой способ построения графов представляется менее трудоемким.


Библиографическая ссылка

Белаш А.Н. О СПОСОБАХ ПОСТРОЕНИЯ РЕГУЛЯРНЫХ ГРАФОВ // Современные наукоемкие технологии. – 2012. – № 12. – С. 54-54;
URL: https://top-technologies.ru/ru/article/view?id=31149 (дата обращения: 29.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674