An introduction to graph theory concluding with an introduction to automata and formal languages.

Graph Theory

• Generality: oriented and un-oriented graphs, valued graphs, sub-graphs, degree, chain, path, connexity, strong connexity
• Graph traversal: Depth-first search, Breadth-first search
• Shortest path: Dijkstra algorithm
• Maximal flow problem: Flow, Cut, Maximum flow, Minimal cut, Ford-Fulkerson algorithm

Formal Languages

• Alphabet and words
• Regular language, regular expressions

Automata

• Synchronus and Asynchronus automata
• Determinist automata
• Automata and regular languages
• Unambiguous finite automata