2026/2027
Просто о сложных сетях 1
Статус:
Дисциплина общефакультетского пула
Кто читает:
Факультет математики
Где читается:
Факультет математики
Когда читается:
1, 2 модуль
Охват аудитории:
для всех кампусов НИУ ВШЭ
Преподаватели:
Тужилин Михаил Алексеевич
Язык:
английский
Кредиты:
6
Контактные часы:
60
Course Syllabus
Abstract
The course is devoted to the fundamentals of graph theory and complex networks. It starts with the main concepts of basic graph theory and ends with its modern scientific directions.
Expected Learning Outcomes
- Basic definitions, types of graphs, isomorphism
- Algebraic concepts: adjacency and incidence matrices, adjacency matrix degree theorem
- Laplacian matrix, Matrix Tree Theorem, Cayley's formulas
- Basic algorithms of graphs
- Planarity and polyhedrons
- Vertex and edge connectivity, Mengers theorem, theorem about (k, l, d)-graph, Tarjan's algorithm
- Eulerian and Hamiltonian graphs
- Relations between planarity and k-connectivity
- Duality and dual polyhedrons, Steinitz theorem, Lie algorithm
- Flows, decomposition theorem, Ford-Fulkerson theorem, max-flow algorithm
- Introduction in spectra
- infinite serieses: star graphs, wheel graphs, windmill graphs, nested triangles graph
- Small-world networks, average shortest path length and clustering coefficients
- Relations between characteristics
- Barabási–Albert model and properties
- The Pontryagin–Kuratowski theorem on subdivisions and the Auslander–Parter planarity testing algorithm
- Real and artificial networks, small-world and scale-free properties, centralities
- Models of real networks: Watts-Strogatz, Barabasi-Albert and others
- Random networks, Erdos-Renyi model and properties
- Introduction to probability theory
Course Contents
- Introduction in graph theory. Basic structures of complex networks and their definitions
- Local and global characteristics of networks, infinite serieses of networks
- Introduction tо probability graph theory
Assessment Elements
- HomeworkOur course is divided into several parts such as -Introduction to graph theory -Graphs and Matrices -Spectral graph theory -Random Graphs -Dynamics on graphs After each part the list of problems will be provided
- Test
Interim Assessment
- 2026/2027 2nd moduleFinal grade for the course – at the end of the entire course. The maximum score is 150, which is calculated as 100×W + 50×E, where W is the coursework grade (based on work throughout all four modules, including homework, seminar participation, and tests), and E is the final exam grade at the end of the year.
Bibliography
Recommended Core Bibliography
- Graph theory, Bondy, J. A., 2008
- J. A. Bondy, & U. S. R. Murty. (1976). Graph theory with applications. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.CB6871BA
- Modern graph theory, Bollobas, B., 2009
- Networks : an introduction, Newman, M. E. J., 2013
- Random graphs, Bollobas, B., 2001