Complexity and Networks
Faculteit | Science and Engineering |
Jaar | 2020/21 |
Vakcode | WMMA005-05 |
Vaknaam | Complexity and Networks |
Niveau(s) | master |
Voertaal | Engels |
Periode | semester I a |
ECTS | 5 |
Rooster | rooster.rug.nl |
Uitgebreide vaknaam | Complexity and Networks | ||||||||||||||||||||||||||||||||
Leerdoelen | At the end of the course, the student is able to: 1. inspect whether a given graph is planar, Euler and unicursus; whether two given graphs are isomorphic; whether a given graph is bipartite; 2. construct a maximal matching for a given bipartite graph and on its basis, find a largest matching by applying Berge's magnifier; 3. find a maximal traffic flow in a transport network, not exceeding a given list of capacities; evaluate the transport capacity of a network cut, construct the increment graph and realise the Ford--Filkerson algorithm for finding a largest flow in a given network. Using the scheme for finding largest flows, find a least flow that exceeds the given loads; 4. bound controllable space by using graph partitions, verify whether a given set of nodes is a zero forcing set and apply the theory to specific classes of graphs in order to select leaders rendering the system controllable; 5. mathematically describe random graphs in terms of properties like connected components, average degree and diameter, is familiar with major examples like the Erdös-Renyi graph, the configuration model and the preferential attachment graph and is able to follow the proof of phase transition for connectivity in the Erdös-Renyi graph. |
||||||||||||||||||||||||||||||||
Omschrijving | This is an interdisciplinary course that presents different aspects of the theme Complexity and Networks from both the pure and applied mathematics points of view. The course consists of three parts. Part I of the course, by A.V.Kiselev, is Introduction to graphs and network flows. In three weeks, we study: * the notion of (un)directed graphs and graph isomorphisms, planar graphs (criterion), Euler and unicursus graphs (the Koenigsberg bridges problem); * bipartite graphs (Koenig's criterion), partitioning by using breadth first search, matchings (perfect, maximal, largest), the assignment problem (tourist guides and tourist groups) and Hall's theorem, Berge's magnifier theorem about finding a largest matching from a given maximal matching; * networks and network flows (maximal flow, largest flow, capacities and loads, least flow), the algorithm for finding a maximal flow; network cuts, the increment graph and the Ford--Fulkerson algorithm for finding a largest flow by using a given maximal flow. (The least flow problem is a bonus.) In the second part, by K. Camlibel, the notion of system controllability is discussed with emphasis on systems defined on graphs, diffusively coupled leader/follower systems, and concepts such as controllable space, leader selection, and targeted controllability. In the third part, by D. Valesin, the topic is the Erdös-Renyi random graph model; the main result that is stated and proved is the phase transition, with respect to the connectivity probability parameter, of the size of the largest connected component of this graph. |
||||||||||||||||||||||||||||||||
Uren per week | |||||||||||||||||||||||||||||||||
Onderwijsvorm | Hoorcollege (LC), Werkcollege (T) | ||||||||||||||||||||||||||||||||
Toetsvorm |
Opdracht (AST)
(The assessment consists of 3 homework assignments, one for each part of the course. The final grade is the average of the grades of the 3 homework grades, provided that all grades are above 4. If one of the homework grades is 4 or less then the final grade is the minimum of the homework grades.) |
||||||||||||||||||||||||||||||||
Vaksoort | master | ||||||||||||||||||||||||||||||||
Coördinator | prof. dr. D. Rodrigues Valesin | ||||||||||||||||||||||||||||||||
Docent(en) | prof. dr. M.K. Camlibel , A.V. Kiselev ,prof. dr. D. Rodrigues Valesin | ||||||||||||||||||||||||||||||||
Verplichte literatuur |
|
||||||||||||||||||||||||||||||||
Entreevoorwaarden | The course assumes prior knowledge in: - Real and complex analysis - Probability theory - Linear algebra (vector spaces, invariant subspaces, quotient spaces, eigenvalues, eigenvectors) - Fourier series - Dynamical systems (equilibria, linear stability) - Systems theory (state and controllability) - Programming skills |
||||||||||||||||||||||||||||||||
Opmerkingen | Literature: Part 1: References: - Introduction to Modern Dynamics: Chaos, Networks, Space and Time. D. D. Nolte, Oxford University Press, 2015. - Synchronization in Complex Networks. A. Arenas, A. Díaz-Guilera, J. Kurths, Y. Moreno, C. Zhou, Physics Reports, vol. 469, pp. 93-153, 2008. Part 3: Main reference: - Van Der Hofstad, Remco. "Random graphs and complex networks." Available on http://www.win.tue.nl/rhofstad/NotesRGCN.pdf (2009). Additional reference: - Durrett, Richard. Random graph dynamics. Vol. 200, no. 7. Cambridge: Cambridge university press, 2007. Part 4: Reference: - Notes on Rigidity Theory, James Cruickshank This course was registered last year with course code WMMA16000 |
||||||||||||||||||||||||||||||||
Opgenomen in |
|