combinatorialmethods

Page 1

• Title and Authors: Combinatorial Methods and Algorithms by Zsolt Tuza, Csilla Bujtás, Máté Hegyháti, 2014.

• Project Information: Developed under the TÁMOP-4.1.2.A/1-11/1-2011-0088 project by the Pannon University and Miskolc University.

• Contact:

  • Address: H-8200 Veszprém, Egyetem u. 10; H-8201 Veszprém, Pf. 158.

  • Phone: (+36 88) 624-911; Fax: (+36 88) 624-751.

  • Internet: www.uni-pannon.hu

• Project Aim: Innovative logistics training development through e-learning as a center of logistics in Eastern Europe.

Page 2

• Contents Overview:

  • Preface (8)

  • Basic graph theory (10)

    • Basic definitions (10)

    • Special significant graphs (22)

    • Graph parameters (25)

    • Graph extensions (50)

    • Complexity of algorithms (55)

  • Interval systems (58)

  • Other chapters on various systems, algorithms, and problems leading to advanced concepts.

Page 3

• Continued Contents:

  • Chordal graphs (78)

  • Tree decompositions of graphs (85)

  • Maximum matchings in bipartite graphs (110)

  • Extreme problems (169)

• Further Reading: Books and articles suggested for deeper understanding.

Page 4

• Edge Decompositions: Discussion of the methods used to decompose graphs into edge substructures and their significance in combinatorial optimization.

• Examples: Various practical implementations within the context of applications in logisitics and optimization.

Page 5

• Figures and Illustrations: Visual representations of graphs, including undirected graphs, tree-like layouts, matching numbers, and transversals in set systems.

• General Notes on Algorithms: Emphasis on theoretical foundations and proofs through illustrations.

Page 6

• Properties of Set Systems: Details on how properties of finite systems and intersection graphs correlate with their combinatorial properties.

• Use of Algorithms in Graph Theory: Discusses algorithms for determining properties like independence number and matching number, with complex examples illustrated.

Page 7

• Projective Plane Concept: Introduction of concepts relating geometry to combinatorial structures, particularly in finite projective planes and their properties in graph theory.

• Applications: Suggested applications in fields like network design, optimization problems in logistic systems, etc.

Page 8

• Complexity and Algorithmic Challenges: Overview of difficult problems within graph theory, especially about bipartite graphs and their decompositions.

• Performance and Efficiency: Discussion on how tree decompositions can help in finding solutions more efficiently.

Page 9

• Illustration of Algorithms: Details on how algorithms function in practice, with step-by-step breakdowns and examples related to maximum matchings and colorings.

• Discussion on Kernel Properties: Overview of approaches to identify kernels in directed graphs and their significance.

Page 10

• Specific Topics in Graph Theory: Discussion of Turán's theorem, Kőnig's theorem, and properties of perfect graphs.

• Combinatorial Applications: Connection of theoretical graph properties with real-world logistic optimization challenges.