﻿ Graph algorithm-清华大学求真书院

### Graph algorithm

Record: No

Language: Chinese

Prerequisite

Discrete math.

Abstract

In this course, we introduce basic concepts in graph theory and complexity theory, then study graph algorithms with a focus on matching and network flows.

Reference

1. Introduction to Graph Theory, by Douglas B. West.

2. Modern Graph Theory, by Bela Bollobas.

3. The Design and Analysis of Algorithms, by Dexter Kozen.

Syllabus

(Tentative)

- Foundamental concepts: graphs, paths, walks, cycles, trees, isomorphism, adjacency matrix, complexity classes, reduction, completeness, …

- Matching: bipartite maximum matching, bipartite minimum-cost perfect matching, Primal-dual min-cost matching, online maching…

- Flow: max-flow min-cut theorem, Ford-Fulkerson and Edmonds-Karp algorithms, Dinitz's algorithm, Hopcroft-Karp algorithm, Menger's theorem…

- NP-complete problems: max-cut, independent set, …

- Approximate algorithms: vertex cover, max-cut, graph coloring, …

- Spectural graph theory: Courant-Fischer theorem, graph Laplacian, Cheeger's inequality, graph sparsification, …

Lecturer Intro

Lecturer Email: hanru@bimsa.cn

TA: Dr. Chuqi Cao, chuqicao@bimsa.cn

• ### The chromatic profile of a graph

AbstractDetermining the chromatic number of a graph is a difficult but important problem. Hence, it is not surprising that a variety of questions in Graph Theory concern the search for meaningful upper bounds for the chromatic number of certain families of graphs. One type of graph family that received considerable attention is that of H-free graphs, that is, the family of graphs G which do not...

• ### Graph Theory

Record: YesLevel: GraduateLanguage: EnglishPrerequisiteAbstractThe goal of this course is to give students an overview over the most fundamental concepts and results in modern graph theory.The topics which we plan to cover include: Basic notions: graphs, graph isomorphism, adjacency matrix, paths, cycles, connectivityTrees, spanning trees, Cayley's formula,Vertex and edge connectivity, 2-connec...