Complexity and Networks
Faculteit  Science and Engineering 
Jaar  2020/21 
Vakcode  WMMA00505 
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 FordFilkerson 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ösRenyi graph, the configuration model and the preferential attachment graph and is able to follow the proof of phase transition for connectivity in the ErdösRenyi 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 FordFulkerson 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ösRenyi 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íazGuilera, J. Kurths, Y. Moreno, C. Zhou, Physics Reports, vol. 469, pp. 93153, 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 
