

授業科目 Course Title 
グラフ理論特論

Ｓｐｅｃｉａｌ Ｔｏｐｉｃｓ ｉｎ Ｇｒａｐｈ Ｔｈｅｏｒｙ

担当者 Instructor 
准教授 ボサール アントワーヌ  後学期 金曜日2時限 

単 位 Credit 
2 





関連するディプロマポリシー Related Diploma Policy

国際的感性とコミュニケーション能力/International sensibilities and communication capabilities 時代の課題と社会の要請に応えた専門的知識と技能/Expert knowledge and skills to address the issues of the age and the demands of society



到達目標 Target to be Reached

Precise knowledge of graph theory definitions and notations. For instance, understanding the degree and diameter of a graph, spanning trees, graph morphisms. Ability to program graph traversal algorithms and path selection (routing) algorithms. Also, gaining a precise understanding of the definition of network topologies such as hypercubes.


授業内容 Course Content

Graph theory is ubiquitous in computer and information science. Data structures, optimisation, parallel computing are only a few examples of areas strongly relying on graph theory. It is thus very important for computer scientists to be knowledgeable in this field.
The objective of this course is to first present to students important and various aspects of graph theory, including paths, cycles, diameter, matchings and so on. The second objective is to describe concrete applications of graph theory, especially in the field of interconnection networks of parallel systems. Network topologies, routing algorithms, faulttolerance and so on will be discussed in the second part of this course.


授業計画 Course Planning

Note that the following lecture plan may be slightly adjusted upon needs. As homework, in preparation for the next lecture, students are advised to carefully read and study the materials presented and discussed during each lecture.
Part 1: A few important topics of graph theory.
1. Guidance, introduction, motivation Introducing graph theory: basic definitions, applications.
2. Definitions and notations Formally recalling graphs and important notations.
3. Remarkable graph properties On degrees, connectivity, spanning trees, Euler tours.
4. Paths and cycles, distance and diameter. Hamilton cycle, Hamilton path.
5. Graphs algorithms (1) Depthfirst search, Breadthfirst search.
6. Graphs algorithms (2) Dijkstra algorithm, and others.
7. rpartite graphs, matchings (1) Bipartite graphs, matching definition.
8. Matchings (2) The marriage condition and Hall's theorem.
9. Midterm evaluated practice Test (60min) and aftertest discussion (30min).
Part 2: Application to networks.
1. Hypercubes Definition, topological properties, simple routing.
2. Hypercubes: algorithms Gray code and Hamiltonian cycles, about faulttolerance, faulttolerant pointtopoint routing, the container problem.
3. Hierarchical networks (1) Definitions, properties, applications (supercomputing: massively parallel systems).
4. Hierarchical networks (2) Routing strategies, additional network topologies.
5. Final examination Test (60min) and aftertest discussion (30min).


授業運営 Course Management

As usual for graduate lectures, this course will be given in English.


評価方法 Evaluation Method

Midterm examination: 40%. Final examination: 60%. Absence to 5 lectures (or more) will result in an automatic 0 (zero) score to the course evaluation (no credit given).


オフィスアワー Office Hour (s)

Friday 10am11am, 6231.


使用書 Textbook (s)

R. Diestel『Graph Theory』4th[SpringerVerlag Heidelberg, New York]2010
(electronic edition available online at no charge: http://diestelgraphtheory.com/basic.html)






