Восстановить пароль
FAQ по входу

Ruohonen K. Graph Theory

  • Файл формата pdf
  • размером 612,70 КБ
  • Добавлен пользователем
  • Отредактирован
Ruohonen K. Graph Theory
Tampere University of Technology, 2006, -115 pp.
These lecture notes were translated from the Finnish lecture notes for the TUT course Graafiteoria. The laborious bulk translation was taken care of by the students Janne Tamminen (TUT) and Kung-Chung Lee (visiting from the University of British Columbia). Most of the material was then checked by professor Robert Piché. I want to thank the translation team for their effort.
The notes form the base text for the course MAT-41196 Graph Theory. They contain an introduction to basic concepts and results in graph theory, with a special emphasis put on the network-theoretic circuit-cut dualism. In many ways a model was the elegant and careful presentation of SWAMY & THULASIRAMAN, especially the older (and better) edition. There are of course many modern text-books with similar contents, e.g. the popular GROSS & YELLEN. One of the usages of graph theory is to give a unified formalism for many very differentlooking problems. It then suffices to present algorithms in this common formalism. This has lead to the birth of a special class of algorithms, the so-called graph algorithms. Half of the text of these notes deals with graph algorithms, again putting emphasis on network-theoretic methods. Only basic algorithms, applicable to problems of moderate size, are treated here. Special classes of algorithms, such as those dealing with sparse large graphs, small-world graphs, or parallel algorithms will not be treated. In these algorithms, data structure issues have a large role, too (see e.g. SKIENA).
The basis of graph theory is in combinatorics, and the role of graphics is only in visualizing things. Graph-theoretic applications and models usually involve connections to the real world on the one hand—often expressed in vivid graphical terms—and the definitional and computational methods given by the mathematical combinatoric and linear-algebraic machinery on the other. For many, this interplay is what makes graph theory so interesting. There is a part of graph theory which actually deals with graphical drawing and presentation of graphs, briefly touched in Chapter 6, where also simple algorithms are given for planarity testing and drawing. The presentation of the matter is quite superficial, a more profound treatment would require some rather deep results in topology and curve theory. Chapter 7 contains a brief introduction to matroids, a nice generalization and substitute for graphs in many ways.
Proofs of graph-theoretic results and methods are usually not given in a completely rigorous combinatoric form, but rather using the possibilities of visualization given by graphical presentations of graphs. This can lead to situations where the reader may not be completely convinced of the validity of proofs and derivations. One of the goals of a course in graph theory must then be to provide the student with the correct touch to such seemingly loose methods of proof. This is indeed necessary, as a completely rigoristic mathematical presentation is often almost unreadable, whereas an excessively slack and lacunar presentation is of course useless.
Definitions and Fundamental Concepts
Directed Graphs
Matrices And Vector Spaces of Graphs
Graph Algorithms
Drawing Graphs
  • Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.
  • Регистрация