это быстро и бесплатно
Оформите заказ сейчас и получите скидку 100 руб.!
ID (номер) заказа
3391492
Ознакомительный фрагмент работы:
Основные понятия
Пусть задан граф в стандартной форме G = {V, E}, где V – множество вершин графа, Е – множество рёбер, состоящее из пар вида (х, у), где х, у принадлежат V.
Дерево – связный граф, не имеющий циклов. Другое определение: связный граф порядка n, имеющий (n-1) ребро.
Степень вершины графа – число инцидентных вершине рёбер.
k-арное дерево – дерево, степень каждой вершины которого не более (k+1). Другое определение: дерево, у каждой вершины которого не более k потомков.
Как следует из определения, любое k-арное дерево является также (k+m)-арным деревом, m>0. Также следует, что у графа порядка n есть несколько k-арных деревьев.
Будем считать, что у k-арного дерева хотя бы одна вершина имеет или степень (k+1), или степень (n-1).
Один из способов построения:
- задано множество вершин V = {v1, v2, …, vn} и арность k;
- если , то добавляем в Е рёбра вида , конец.
- иначе добавляем в Е ребра вида , а затем добавляем в Е ребра вида , конец.
Подробный алгоритм
Перенумеруем вершины в произвольном порядке. Будем считать, что в качестве входных данных используется число вершин (порядок графа) N и требуемая арность K . На выходе необходимо получить перечисление рёбер графа. Рёбра будем представлять в виде пар номеров вершин.
Запишем алгоритм в следующем виде:
Шаг 0. k = K, n = N – 1.
Шаг 1. Если n = 0, то конец.
Шаг 2. Если k = 0, то добавить ребро , n = n – 1, на шаг 1.
Шаг 3. Добавить ребро , k = k – 1, n = n – 1, на шаг 1.
1. Задание исходных данных
Исходное дерево задаётся порядком и арностью:
% graph order
vertex(4).
% arnostarity(2).
2. Добавление рёбер
Создадим правило edge(n, k, N), которое будет строить рёбра. Реализация на Прологе шага 1:
% make new edgeedge(0, _, _).
Добавим шаг 2:
edge(N, 0, Nmax):-
N1 is N + 1,
A is [N, N1],
write(A), nl,
N2 is N - 1,
edge(N2, 0, Nmax).
Реализация шага 3:
edge(N, K, Nmax):-
A is [N, Nmax],
write(A), nl,
N1 is N - 1,
K1 is K - 1,
edge(N1, K1, Nmax).
3. Программа на Прологе
Реализовано на Strawberry Prolog v.3.0 с проверкой входных данных.
% goal
?- vertex(V),
vertex(N),
arity(K),
write("Graph order: "),
write(N), nl,
write("Tree arity: "),
write(K), nl, nl,
N > 1,
K > 0,
N1 is N - 1,
K1 is K + 1,
edge(N1, K1, N).
% database
% graph order
vertex(6).
% arnostarity(1).
% predicates
% make new edge
edge(0, _, _).
edge(N, 0, Nmax):-
N1 is N + 1,
A is [N, N1],
write(A), nl,
N2 is N - 1,
edge(N2, 0, Nmax).
edge(N, K, Nmax):-
A is [N, Nmax],
write(A), nl,
N1 is N - 1,
K1 is K - 1,
edge(N1, K1, Nmax).
4. Тестирование программы
1) 1-арное дерево
Graph order: 6
Tree arity: 1
[5,6]
[4,6]
[3,4]
[2,3]
[1,2]
Yes.
2) бинарное дерево
Graph order: 6
Tree arity: 2
[5,6]
[4,6]
[3,6]
[2,3]
[1,2]
Yes.
3) арность больше порядка графа
Graph order: 6
Tree arity: 8
[5,6]
[4,6]
[3,6]
[2,6]
[1,6]
Yes.
4) недопустимые значения входных данных
Graph order: 6
Tree arity: 0
No.
Graph order: 1
Tree arity: 2
No.
Сделайте индивидуальный заказ на нашем сервисе. Там эксперты помогают с учебой без посредников 
Разместите задание – сайт бесплатно отправит его исполнителя, и они предложат цены.
Цены ниже, чем в агентствах и у конкурентов
Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит
Бесплатные доработки и консультации
Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки
Гарантируем возврат
Если работа вас не устроит – мы вернем 100% суммы заказа
Техподдержка 7 дней в неделю
Наши менеджеры всегда на связи и оперативно решат любую проблему
Строгий отбор экспертов
К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»
Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован 
Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн 
Выполнение 6 работ в программе Statistica
Контрольная, Программные статистические комплексы
Срок сдачи к 20 февр.
Написать на 15 стр анализ организации процесса бюджетирования и разработку предложений по оптимизации структуры и формирования бюджетов ооо «стройкомплекс»
Контрольная, Финансовое планирование и бюджетирование в деятельности предприятий
Срок сдачи к 22 янв.
Контрольная под дисциплине Механика жидкости и газа
Контрольная, Механика жидкости и газа
Срок сдачи к 20 янв.
Социальное и общечеловеческое в конфликте поколений в романе И. С
Курсовая, Литература
Срок сдачи к 23 янв.
Контрольная работа "Расчёт теплопритоков в охлаждаемую камеру"
Контрольная, Теплотехника и хладотехника
Срок сдачи к 19 янв.
Дипломная работа по теме "разработка программы лояльности и клиентоориентированности для повышения продаж гостиничного продукта на примере гостиницы doubletree moscow arbat"
Диплом, Гостиничное дело
Срок сдачи к 17 апр.
Лабораторная работа № 1.1 Модуль: Основы логического мышления
Решение задач, Введение в специальность, логика
Срок сдачи к 15 янв.
сделать лабораторные работы
Лабораторная, Цифровая культура в профессиональной деятельности, культурология
Срок сдачи к 25 янв.
«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами
Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:
Принимаем к оплате
© 2011—2026 Всё сдал!
Заполните форму и узнайте цену на индивидуальную работу!
Мы ВКонтакте 
Трейлер о сайте