DonNTU   Masters' portal

Abstract

Table of Contents

Introduction

The most important property of the information model and control system is its structure, or, in mathematical terms, the set of binary relations on a set of elementary data items and actions. These data structures and operations are the only structure essences programs and data processed by them, in which they can exist in the imagination of the programmer and the computer in the womb.

Description of the subject area

Graph theory is of great importance in modern mathematics and computer worlds, which makes it important to improve the quality of training in technical fields. Also, the graphs are widely used in other fields of scientific endeavor, such as psychologists people are vertices and edges - it is their relationship with each other.

Graph-theoretic approach is also used in the rapidly developing field of linear programming and operations research in the study of flows in networks.

The urgency of the problem

Object of study : practical exercises on a training course «Graph theory».

Subject of study : intellectual methods of automatic generation of graphs.

The theoretical part

In order to implement the automatic generator of case studies for the course «Graph theory», it is necessary to study the structure of educational material, the content of the main sections and highlight the skills and abilities that students should learn after each section.

Concepts of «Graph theory»

Two vertices are called adjacent if they are connected by an edge.

Two edges are called adjacent if they share a vertex.

Denote the edge of the graph: e = (u, v), where u and v - end vertices of the edge. Edge e incident to a vertex v, if the vertex v is one of the end vertices of the edge e.

Note that the neighborhood is a relation between the homogeneous elements of the graph, while the incidence is the ratio between disparate elements.

If the set V is finite, then the graph is finite. Next, we will only talk about the final graphs. >

Methods of specifying graphs

Here are the main ways to specify graphs:

Graphs for the practical tasks

Picture 1 (animation - 81 frames, 10 reps)

Displaying requirements change graphs

The basic requirements for a practical tasks

On the basis of the tasks in the laboratory, to the generated graph formed certain requirements for each topic the requirements. All specifications and recommendations are based on the characteristics of each section of the course "Theory of graphs" and are chosen so that the student first (second) rate could perform laboratory and at the same time, the task will not be too easy, that is, student will be able to apply all of the skills on the subject and learn how to use a creative approach to all problems in the future.

Planned practical results

Today, there are several algorithms for generating random graphs using techniques and artificial intelligence, for example, by means of genetic algorithms. But a detailed description of the sources of mass access at the moment there.

Its research and development in the direction of the automatic generation of graphs I plan follows:

1. For each section of the course "Graph theory" to explore the adjacency matrix and intsedentnosti

2. Identify and map for each matrix pattern

3. On the basis of these laws to develop an algorithm for generating graphs of each section

4. After analyzing the properties of adjacency matrices and intsedentnosti, the ability to generate a universal graph - graph that will meet the requirements in several sections of the "Theory of graphs»

5. After optimization of the algorithms to develop a program that allows a student or a teacher he needs Generate a graph that will be displayed in the form of co-occurrence matrices and intsedentnosti. Generation will occur individually, depending on the student's first and last name, which he will enter in the appropriate fields. When re-entering the data will be generated by the same count as when you first enter.

For each section of the course to its generation algorithm, as taken separately section requires certain skills to perform the laboratory, and from that go out every algorithm for generating graphs.

Create a highly individual variants in laboratory eliminates cheating and forces students to work independently. This increases the percentage of mastery of the material gets angry because everyone will have to understand the material before starting any job.

I guess I should be used as an identifier name of the student, ie, a number to each letter of name will mean the number of vertices and edges within acceptable ranges and regular arrangement of edges in the graph.

Conclusions

The study on "Development and research of methods of automatic generation of practical problems on the training course" Graph Theory, "" I found out that this course is very important for the technical professions (and not only for technical) as well as graph theory is widely used in various fields such as programming, design, physics, chemistry, etc.. Also, the process of studying this course contributes to the development of logical and abstract thinking, and learning in the non-standard approach to the solution of various problems.

Currently, the conventional algorithm for generating a random graph does not exist. Therefore, I consider topical consider such an algorithm. For each section of the course to its generation algorithm, as taken separately section requires certain skills to perform the laboratory, and from that go out every algorithm for generating graphs.

In writing this essay master's work is not yet complete. Final completion: December 2013. Full text of the and materials on the topic can be obtained from the author or his manager after that date.

References

  1. Уилсон. Р. Введение в теорию графов / Г.П. Гаврилов. – Москва: Мир, 1957. – 450 с.
  2. Оре. А. Теория графов / А. Оре. – Москва: Наука, 1980. – 348 с.
  3. Берж. К. Теория графов и ее применение / К. Берж. – Москва: Иностранная литература, 1962. – 432 с.
  4. Андреев. В.В. Информационная система управления вузом / В.В. Андреев. – Рязань: Полиграфия, 2010. – 282 с.
  5. Харари. Ф. Теория графов / Ф. Харари. – Москва: Мир, 1973. – 380 с.
  6. Евстигнеев. В.А. Применение теории графов в программировании / В.А. Евстигнеев. – Москва: Наука, 1980. – 355 с.
  7. Информационные технологии в учебном процессе: сб. наук. пр. / сост.: М.И. Жолдак и др..; Юго-укр. гос. пед. ун-т им. К.Д. Ушинского. – Одесса: Астропринт, 2007. – 167 с.
  8. Щеголов. В.И. Этническое в психологическом поле студента: монография / В.И. Щеголов. – СПб.: Астерион, 2004. – 91 с.
  9. Исаенко А.А. Электронные научно-информационные ресурсы / А.А. Исаенко / / Документоведение: материалы IV Междунар. научно-практической. конф. – Киев, 2007. – С. 179-180.
  10. Гордукалова. Г.Ф. Информационный мониторинг / Г.Ф. Гордукалова, В.А. Минкина / / Стратегическое использование информационных систем: материалы Междунар. семинара. – СПб., 1992. – С. 52-54
  11. Дайнеко В. Интеллектуальные продукты / В.Г. Дайнеко / / Вестн. Воронеж. гос. техн. ун-та. Ср. Гуманитарные науки. – 2005. – Вып. 94. – С. 19-20.
  12. Simon. Н.А.Information-processingmodelsofcognition / / J. Amer. Soc. InformationScience. Sept. 1981. – 208 p.
  13. Линдсей П., Норман Д. Переработка информации у человека / Под ред. А.Р. Лурия. Москва: Мир, 1974. – 345 с.
  14. Грунский И.С. Об алгебре языков, представимых графами с отмеченными вершинами / И.С. Грунский, Е.А. Пряничникова // Труды Ин-та прикл. математики и механики НАН Украины. – 2009. – т.18. – С. 37-46.
  15. Пряничникова Е.А. Характеризация языков, представимых в графах с отмеченными вершинами / Е.А. Пряничникова // Труды Ин-та прикл. математики и механики НАН Украины. – 2010. – т.19. – С. 37-46.