# 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
OrientationAttendance TypeSemesterYearECTS
CoreElective CoursesSpring-5

 Academic Year 2021 – 2022 Class Period Spring Instructors from Other Categories Vasileios Karagiannis 39hrs 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
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
Lectures391.3
Exams30.1
Total1505
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, Πανεπιστήμιο Αθήνας