

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

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

担当者 Instructor 
助教 ボサール アントワーヌ  後学期 月曜日1時限 

単 位 Credit 
2 





到達目標 Target to be Reached

Precise knowledge of graph theory definitions and notations. For instance, understanding what is the degree and diameter of a graph, a spanning tree, a graph morphism. Ability to program graph traversal algorithms and path selection (routing) algorithms. Also, concrete 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, etc. 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, ranging from paths, cycles and diameter to extremal and random graphs. 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, etc. 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 slides/materials presented and discussed during each lecture.
Part 1: A few important topics of graph theory.
1. Guidance, introduction, motivation
This lecture's syllabus will be reviewed and discussed.
2. Definitions and notations
Formally recalling trees and graphs. Paths, cycles, distance and diameter.
3. Remarkable graph properties
On degrees, connectivity, spanning trees, Euler tours.
4. Graphs algorithms
DFS, BFS, cycle detection…
5. Bipartite graphs, matchings and Hall’s (marriage) theorem
And a few words on Hamiltonicity, laceability.
6. Planar graphs and colouring
Properties and maps colouring.
7. Graph morphisms
Graph homomorphism, isomorphism, automorphism and application to symmetric graphs.
8. Extremal graphs
Turán’s theorem, ErdősSós conjecture.
9. About random graphs
Applications, definitions, properties.
10. Midterm examination
Test (60min) and aftertest discussion (30min).
Part 2: Application to networks.
1. Hypercubes
Definition, topological properties.
2. Hypercubes: algorithms
Simple routing, Gray code, the container problem.
3. About faulttolerance
With examples on the hypercube.
4. Hierarchical networks
They are popular in supercomputing and massively parallel systems.
5. Routing in hierarchical networks
Discussing main strategies.
6. 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 credits given).


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

Questions and remarks can be made individually at the end of each lecture.


使用書 Textbook (s)

Lecture slides will be uploaded each week on dotCampus.

参考書 Book (s) for Reference

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





