Алгоритм расчета степеней вершин графа

 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Сибирский государственный технологический  университет

Кафедра системотехники 

ЗАДАНИЕ

НА  РАСЧЕТНО-ГРАФИЧЕСКУЮ РАБОТУ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ 

      Студент

      Факультет

      Тема: Исследование и программная реализация методов и алгоритмов теории графов. 
 

      Вариант 47

         Алгоритм расчета степеней вершин графа. 

         Предложенную задачу сформулировать в терминах теории графов и подобрать соответствующий  алгоритм.

         Реализовать выбранный  алгоритм на языке Pascal. Предусмотреть возможность ввода разнообразных входных данных.

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

         Приложить распечатки экранов. 
 
 
 
 
 
 
 
 
 
 
 
 

 

      

      СОДЕРЖАНИЕ 

      Реферат

      Введение

      1.Степени  вершин графа

      2 Решение задачи

            2.1 Входная и выходная информация

            2.2 Схема алгоритма

            2.3 Текст программы

            2.4 Протокол контрольного  расчета

      3 Инструкция по работе с программой

      Заключение

      Список  используемых источников 

 

Реферат 

      Расчетно-графическая  работа представляет собой решение  задачи по расчету степеней вершин графа. Расчет выполнен с помощью языка программирования Delphi 7.0 на ПК Genuine Intel(R) CPU T1400 1.83GHz.

      Ключевые  слова: граф, степени вершин графа.

      Пояснительная записка включает в себя 15 страниц, 1 распечатку экрана, схему алгоритма,  3 использованных литературных источника.

      Цель  работы – овладение навыками нахождения степеней вершин графа.

      Метод исследования – теория графов, алгоритмизация, язык программирования Delphi.

      Данная  программа позволяет:

1. ввести граф, используя матрицу смежности;
2. рассчитать степени вершин;

 
 
 

 

ВВЕДЕНИЕ 

      Методы  теории графов применимы во многих сферах жизни общества и производства. Графы широко используются в информатике; достаточно сказать, что схема алгоритма или программы - это ориентированный граф.Вот лишь некоторые сферы их применения:

      Графы и информация.

      Двоичные  деревья играют весьма важную роль в теории информации. Предположим, что  определенное число сообщений требуется  закодировать в виде конечных последовательностей  различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.

      Двоичные  кодовые деревья допускают интерпретацию  в рамках теории поиска. Каждой вершине  при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и  отрицательному ответу соответствуют  два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.

      Таким образом, если кому-то понадобится взять  интервью у различных людей, и  ответ на очередной вопрос будет  зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.

      Графы и химия.

      Еще А. Кэли рассмотрел задачу о возможных  структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:

C_nH_2n+2

      Молекула  каждого предельного углеводорода представляет собой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур  предельных углеводородов, т. е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех.

      Таким образом, подсчет числа гомологов  предельных углеводородов также  приводит к задаче о перечислении деревьев определенного типа. Эту  задачу и ее обобщения рассмотрел Д. Пойа.

      Графы и биология.

      Деревья играют большую роль в биологической  теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность  ветвящихся процессов – размножение  бактерий. Предположим, что через  определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево.

      Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение  одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.

      Графы и физика.

      Еще недавно одной из наиболее сложных  и утомительных задач для радиолюбителей было конструирование печатных схем.

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

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

      Итак, из всего вышесказанного неопровержимо  следует практическая ценность теории графов, доказательство которой и  являлось целью данного параграфа.  

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

 

1 Степени вершин графа 

Степенью  вершины v графа G называется число δ(v) рёбер графа инцидентных вершине v. Если δ(v) = 0, тогда v изолированная вершина, если δ(v) = 1,тогда v висячая вершина. 

2 Решение  задачи 

2.1 Входная и выходная информация 

       Входной информацией программы будет матрица смежности. Выходной информацией программы будет текстовое поле.

2.2 Схема алгоритма 

         

 

2.3 Текст программы 
 

procedure TForm1.B3Click(Sender: TObject);

var n,i,k,j:integer;

    g,m:string;

begin

n:=strtoint(form1.E.Text);

k:=0;

for i:=0 to n-1 do begin

    for j:=0 to n-1 do begin

    if form1.SG.Cells[j,i]='1' then inc(k);

                        end;

    g:=inttostr(k);

    m:=inttostr(i+1);

    form1.M.Lines.Add('Степень вершины V'+m+'='+g);

    k:=0;

                    end;

 

2.4 Протокол контрольного  расчета 

      Введем  число вершин графа равным 6 и зададим матрицу смежности:

        
 
 
 
 
 
 
 
 
 
 
 
 

     Распечатка экрана, соответствующая протокольному расчету 

 

3 Инструкция по  работе с программой 

      Все вводимые данные должны быть целого типа. Для ввода количества вершин графа  должно быть введено натуральное  число не большее 25. Для ввода значений в матрице смежности должно быть введено 1, если вершины связаны или 0, если вершины не связаны. Граф должен быть неориентированным и в нем недолжно быть петель. Для корректной работы на ПК должна быть установлена ОС Windows 98 и выше.

      В начале работы программы необходимо ввести количество вершин графа. Потом последует ввод матрицы смежности  графа. После нажатия кнопки “Определить степени вершин”, на экране в поле “memo” выведутся степени каждой вершины графа.

 

Заключение 

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

      Предложенную  задачу мы сформулировали в терминах теории графов и подобрали алгоритм решения – алгоритм расчета степеней вершины графа.

      Данный  алгоритм был реализован на языке высокого уровня Borland Delphi 7.0. В программе предусмотрена возможность ввода разнообразных входных данных, что позволяет применять данную программу и для решения других подобных задач. 

 

Список  использованных источников 

1. Иванилова Т.Н. Дискретная математика.Ч.1,2.-Красноярск: КГТА, 1995.
2. Новиков Ф.А. Дискретная математика для программистов.-СпбПитер, 2001.
3. Логинов В.В. Введение в дискретную математику.- Калуга, 1998.