Conbinatorics and Graph Theory

Course Information
TitleΣΥΝΔΥΑΣΤΙΚΗ ΚΑΙ ΘΕΩΡΙΑ ΓΡΑΦΗΜΑΤΩΝ / Conbinatorics and Graph Theory
Cycle / Level1st / Undergraduate
Teaching PeriodSpring
CoordinatorVasileios Karagiannis
Course ID600015304

Programme of Study: UPS of School of Mathematics (2014-today)

Registered students: 56
OrientationAttendance TypeSemesterYearECTS
CoreElective CoursesSpring-5

Class Information
Academic Year2019 – 2020
Class PeriodSpring
Instructors from Other Categories
Weekly Hours3
Class ID
Course Type 2016-2020
  • Scientific Area
  • Skills Development
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
  • Face to face
Digital Course Content
The course is also offered to exchange programme students.
Language of Instruction
  • Greek (Instruction, Examination)
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.)
combinatorics, graphs, random graphs
Educational Material Types
  • Notes
  • Slide presentations
  • Multimedia
  • Book
Use of Information and Communication Technologies
Use of ICT
  • Use of ICT in Course Teaching
  • Use of ICT in Communication with Students
PowerPoint presentation of the Theory
Course Organization
Reading Assigment1083.6
Student Assessment
Student Assessment methods
  • Written Exam with Short Answer Questions (Formative, Summative)
  • Written Exam with Extended Answer Questions (Formative, Summative)
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