Conbinatorics and Graph Theory
| Title | ΣΥΝΔΥΑΣΤΙΚΗ ΚΑΙ ΘΕΩΡΙΑ ΓΡΑΦΗΜΑΤΩΝ / Conbinatorics and Graph Theory |
| Code | 0572 |
| Faculty | Sciences |
| School | Mathematics |
| Cycle / Level | 1st / Undergraduate |
| Teaching Period | Spring |
| Coordinator | Vasileios Karagiannis |
| Common | Yes |
| Status | Active |
| Course ID | 600015304 |
Programme of Study: UPS of School of Mathematics (2014-today)
Registered students: 122
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| Core | Elective Courses | Spring | - | 5 |
| Academic Year | 2021 – 2022 |
| Class Period | Spring |
| Instructors from Other Categories |
|
| Weekly Hours | 3 |
| Class ID | 600187145
|
Course Type 2016-2020
- Scientific Area
- Skills Development
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
- Face to face
Digital Course Content
- e-Study Guide https://qa.auth.gr/en/class/1/600187145
Erasmus
The course is also offered to exchange programme students.
Language of Instruction
- Greek (Instruction, Examination)
Prerequisites
General Prerequisites
Knowledge of basics on Linear Algebra, Number Theory and Algebra
Learning Outcomes
1) Knowledge and use of special methods on Counting, Distributing, Partitioning and Divisioning
2) Knowledge and use of Graphs and Random Graphs on the representation of complex systems
General Competences
- Apply knowledge in practice
- Work autonomously
- Work in teams
- Work in an international context
- Work in an interdisciplinary team
Course Content (Syllabus)
1. COUNTING TECHNIQUES: Product Principle, The Sum Principle, Permutations - Lists - Combinations, with and without repetition, Binomial Coefficients, Pigeonhole or Dirichlet Principle, Inclusion-Exclusion Principle, derangements, Reflection Principle, Routs in Grids, The lexicographic permutation order.
2. SPECIAL TOPICS IN COUNTING: The Pascal’s Triangle and the Fibonacci Numbers, Diophantine equations and Partitions, Distribution Problems (Beads in Cells, Stirling's, Bell, Catalan Numbers), Generator Functions.
3. GRAPHS: Basic Concepts (order, size, connectivity, direction, neighbors, walk, path, trail, circle, complement, bipartite graphs, operations, degree, geodesics, distance, diameter, radius), Properties, Matrices, Isomorphism, line graph), Subgraphs, Paths, Trees, Factors, Bridges, Theorems of Kirchhoff, Dirac, Menger. Special Graphs (plane graphs, Euler, Hamilton, n-cubes, Gray Codes, Ramsey Numbers ), Colors (basic theorems, color polynomials, algorithms).
4. INTRODUCTION TO Random Graphs: Erdös-Rényi Networks (Degree Distribution, Average degree, Giant Component, Average Distance, Clustering Coefficient, Transitivity), Introduction to Small World and Scale Free Networks, Introduction to Real Networks, , Centrality: degree, eigenvalue, closeness, betweenness), Examples Using the R Language (Collaboration Networks, Social, Financial, Online, etc.)
Keywords
combinatorics, graphs, random graphs
Educational Material Types
- Notes
- Slide presentations
- Video lectures
- Multimedia
- Book
Use of Information and Communication Technologies
Use of ICT
- Use of ICT in Course Teaching
- Use of ICT in Communication with Students
- Use of ICT in Student Assessment
Description
PowerPoint presentation of the Theory
Video lessons are available on the elearning website
Course Organization
| Activities | Workload | ECTS | Individual | Teamwork | Erasmus |
|---|---|---|---|---|---|
| Lectures | 39 | 1.3 | ✓ | ||
| Reading Assigment | 108 | 3.6 | ✓ | ||
| Exams | 3 | 0.1 | ✓ | ||
| Total | 150 | 5 |
Student Assessment
Student Assessment methods
- Written Exam with Multiple Choice Questions (Formative, Summative)
- Written Exam with Short Answer Questions (Formative, Summative)
- Written Exam with Extended Answer Questions (Formative, Summative)
Bibliography
Course Bibliography (Eudoxus)
1)Μωυσιάδη Πολ.(2001): Εφαρμοσμένη Συνδυαστική. Η τέχνη να μετράμε χωρίς μέτρημα, Εκδ. ΖΗΤΗ, Θεσσαλονίκη.
2)Χαραλαμπίδη, Χ (1990). Συνδυαστική τεύχη 1 και 2, Πανεπιστήμιο Αθήνας
Additional bibliography for study
1)Béla Bollobás (2002). Modern Graph Theory. Springer.
2)West B.D. (2002). Introduction to Graph Theory.
3)Bondy J.A., Murty U.S.R. (2008). Graph Theory. Springer
4)Diestel R. (2005). Graph Theory. Springer, NY.
5)Maarten van Steen (2010). Graph Theory and Complex Networks An Introduction. Maarten van Steen
Last Update
29-05-2021
