457-0925/01 – Graph Theory I (TGI)

 Gurantor department Department of Applied Mathematics Credits 10 Subject guarantor doc. Mgr. Petr Kovář, Ph.D. Subject version guarantor doc. Mgr. Petr Kovář, Ph.D. Study level postgraduate Requirement Choice-compulsory Year Semester winter + summer Study language Czech Year of introduction 1995/1996 Year of cancellation 2009/2010 Intended for the faculties FEI Intended for study types Doctoral
Instruction secured by
KOV16 doc. Mgr. Petr Kovář, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+0
Part-time Credit and Examination 2+0

Subject aims expressed by acquired skills and competences

Each student is supposed to - analyze real life problems - express them as a graph theory problem - solve the problem using graph theory methods - give an interpretation of the theoretical results in the terms of the original problems At the same time he should decide what are the limits of an ideal theoretical solution in contrast to the real situation.

Teaching methods

Lectures
Individual consultations
Tutorials
Project work

Summary

The course covers both basic and advanced topics of Graph Theory, often overlapping with other branches of mathematics (algebra, combinatorics). In the course are many real life problems solved by the methods of graph theory.

Compulsory literature:

D. B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001), ISBN 0-13-0144400-2.

Recommended literature:

Bondy, U.S.R. Murty: Graph Theory with Applications, American Esevier Publishing Co., New York, 1976, ISBN 0-444-19451-7. Behzad, G. Chartrand, L. Lesniak-Foster: Graphs and Digraphs, Prindle, Weber and Schmid, Boston, 197, ISBN 0-87150-261-5.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Přednášky: Grafy a jednoduché grafy. Isomorfismus grafů. Incidenční matice a matice sousednosti. Podgrafy. Stupeň vrcholu. Cesty a cykly. Stromy, mosty a oddělující množiny(řezy). Artikulace. Souvislost grafů, bloky. Párování a pokrytí v grafech a biparitních grafech. Perfektní párování. Hranové barvení. Chromatický index grafu. Vizingova věta. Vrcholové barvení. Chromatické číslo grafu. Brooksova věta. Rovinné grafy. Duální graf. Eulerův vzorec. Kuratowského věta, věta o čtyřech barvách. Orientované grafy. Orientované cesty, orientované cykly. Toky v sítích, řezy. Věta o maximálním toku a minimálním řezu. Eulerovské a Hamiltonovské grafy.

Conditions for subject completion

Full-time form (validity from: 1960/1961 Summer semester, validity until: 2012/2013 Summer semester)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (145) 51
Examination Examination 100  0
Exercises evaluation Credit 45  0
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2009/2010 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2009/2010 (P2645) Electrical Engineering, Communication and Computer systems (3907V001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2009/2010 (P2645) Electrical Engineering, Communication and Computer systems (2642V004) Electrical Machines, Apparatus and Drives P Czech Ostrava Choice-compulsory study plan
2009/2010 (P2645) Electrical Engineering, Communication and Computer systems (2612V015) Electronics P Czech Ostrava Choice-compulsory study plan
2009/2010 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2009/2010 (P2645) Electrical Engineering, Communication and Computer systems (2612V045) Technical Cybernetics P Czech Ostrava Choice-compulsory study plan
2009/2010 (P2645) Electrical Engineering, Communication and Computer systems (2612V015) Electronics K Czech Ostrava Choice-compulsory study plan
2009/2010 (P2645) Electrical Engineering, Communication and Computer systems (2642V004) Electrical Machines, Apparatus and Drives K Czech Ostrava Choice-compulsory study plan
2009/2010 (P2645) Electrical Engineering, Communication and Computer systems (3907V001) Electrical Power Engineering K Czech Ostrava Choice-compulsory study plan
2009/2010 (P2645) Electrical Engineering, Communication and Computer systems (2612V045) Technical Cybernetics K Czech Ostrava Choice-compulsory study plan
2009/2010 (P3646) Geodesy and Cartography (3602V002) Geoinformatics P Czech Ostrava Optional study plan
2009/2010 (P3646) Geodesy and Cartography (3602V002) Geoinformatics K Czech Ostrava Optional study plan
2008/2009 (P2645) Electrical Engineering, Communication and Computer systems (2612V015) Electronics P Czech Ostrava Choice-compulsory study plan
2008/2009 (P2645) Electrical Engineering, Communication and Computer systems (2642V004) Electrical Machines, Apparatus and Drives P Czech Ostrava Choice-compulsory study plan
2008/2009 (P2645) Electrical Engineering, Communication and Computer systems (3907V001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2008/2009 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2008/2009 (P2645) Electrical Engineering, Communication and Computer systems (2612V045) Technical Cybernetics P Czech Ostrava Choice-compulsory study plan
2008/2009 (P2645) Electrical Engineering, Communication and Computer systems (2642V004) Electrical Machines, Apparatus and Drives K Czech Ostrava Choice-compulsory study plan
2008/2009 (P2645) Electrical Engineering, Communication and Computer systems (3907V001) Electrical Power Engineering K Czech Ostrava Choice-compulsory study plan
2008/2009 (P2646) Information Technology K Czech Ostrava Choice-compulsory study plan
2008/2009 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2008/2009 (P2645) Electrical Engineering, Communication and Computer systems (2612V045) Technical Cybernetics K Czech Ostrava Choice-compulsory study plan
2008/2009 (P2612) Electrical Engineering and Computer Science (2612V015) Electronics K Czech Ostrava Choice-compulsory study plan
2008/2009 (P3646) Geodesy and Cartography (3602V002) Geoinformatics K Czech Ostrava Optional study plan
2008/2009 (P3646) Geodesy and Cartography (3602V002) Geoinformatics P Czech Ostrava Optional study plan
2007/2008 (P2645) Electrical Engineering, Communication and Computer systems (2612V015) Electronics P Czech Ostrava Choice-compulsory study plan
2007/2008 (P2645) Electrical Engineering, Communication and Computer systems (2642V004) Electrical Machines, Apparatus and Drives P Czech Ostrava Choice-compulsory study plan
2007/2008 (P2645) Electrical Engineering, Communication and Computer systems (3907V001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2007/2008 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2007/2008 (P2645) Electrical Engineering, Communication and Computer systems (2612V045) Technical Cybernetics P Czech Ostrava Choice-compulsory study plan
2007/2008 (P2102) Mineral Raw Materials (2102V009) Processing K Czech Ostrava Compulsory study plan
2007/2008 (P2102) Mineral Raw Materials (3902V010) Automation of Technological Processes K Czech Ostrava Compulsory study plan
2007/2008 (P2110) Geological Engineering (2101V003) Geological Engineering K Czech Ostrava Compulsory study plan
2007/2008 (P2111) Mining (2101V009) Mining K Czech Ostrava Compulsory study plan
2007/2008 (P3646) Geodesy and Cartography (3602V002) Geoinformatics K Czech Ostrava Compulsory study plan
2007/2008 (P3646) Geodesy and Cartography (3646V001) Mine Surveying and Geodesy K Czech Ostrava Compulsory study plan
2007/2008 (P3904) Engineering Ecology (3904V012) Environment Protection within Industry K Czech Ostrava Compulsory study plan
2006/2007 (P2645) Electrical Engineering, Communication and Computer systems (2612V015) Electronics P Czech Ostrava Choice-compulsory study plan
2006/2007 (P2645) Electrical Engineering, Communication and Computer systems (2642V004) Electrical Machines, Apparatus and Drives P Czech Ostrava Choice-compulsory study plan
2006/2007 (P2645) Electrical Engineering, Communication and Computer systems (3907V001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2006/2007 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2006/2007 (P2645) Electrical Engineering, Communication and Computer systems (2612V045) Technical Cybernetics P Czech Ostrava Choice-compulsory study plan
2005/2006 (P2645) Electrical Engineering, Communication and Computer systems (2612V015) Electronics P Czech Ostrava Choice-compulsory study plan
2005/2006 (P2645) Electrical Engineering, Communication and Computer systems (2642V004) Electrical Machines, Apparatus and Drives P Czech Ostrava Choice-compulsory study plan
2005/2006 (P2645) Electrical Engineering, Communication and Computer systems (3907V001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2005/2006 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2005/2006 (P2645) Electrical Engineering, Communication and Computer systems (2612V045) Technical Cybernetics P Czech Ostrava Choice-compulsory study plan
2004/2005 (P2645) Electrical Engineering, Communication and Computer systems (2612V015) Electronics P Czech Ostrava Choice-compulsory study plan
2004/2005 (P2645) Electrical Engineering, Communication and Computer systems (2612V045) Technical Cybernetics P Czech Ostrava Choice-compulsory study plan
2004/2005 (P2645) Electrical Engineering, Communication and Computer systems (2642V004) Electrical Machines, Apparatus and Drives P Czech Ostrava Choice-compulsory study plan
2004/2005 (P2645) Electrical Engineering, Communication and Computer systems (3907V001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2004/2005 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2004/2005 (P2645) Electrical Engineering, Communication and Computer systems (2612V045) Technical Cybernetics P Czech Ostrava Choice-compulsory study plan
2003/2004 (P2645) Electrical Engineering, Communication and Computer systems (2612V015) Electronics P Czech Ostrava Choice-compulsory study plan
2003/2004 (P2645) Electrical Engineering, Communication and Computer systems (2642V004) Electrical Machines, Apparatus and Drives P Czech Ostrava Choice-compulsory study plan
2003/2004 (P2645) Electrical Engineering, Communication and Computer systems (3907V001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2003/2004 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2003/2004 (P2645) Electrical Engineering, Communication and Computer systems (2612V045) Technical Cybernetics P Czech Ostrava Choice-compulsory study plan
2002/2003 (P2612) Electrical Engineering and Computer Science (2612V015) Electronics P Czech Ostrava Choice-compulsory study plan
2002/2003 (P2612) Electrical Engineering and Computer Science (2612V045) Technical Cybernetics P Czech Ostrava Choice-compulsory study plan
2002/2003 (P2612) Electrical Engineering and Computer Science (2642V004) Electrical Machines, Apparatus and Drives P Czech Ostrava Choice-compulsory study plan
2002/2003 (P2612) Electrical Engineering and Computer Science (3907V001) Electrical power Engineering P Czech Ostrava Choice-compulsory study plan
2002/2003 (P2612) Electrical Engineering and Computer Science (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2001/2002 (P2612) Electrical Engineering and Computer Science (2612V015) Electronics P Czech Ostrava Choice-compulsory study plan
2001/2002 (P2612) Electrical Engineering and Computer Science (2612V045) Technical Cybernetics P Czech Ostrava Choice-compulsory study plan
2001/2002 (P2612) Electrical Engineering and Computer Science (2642V004) Electrical Machines, Apparatus and Drives P Czech Ostrava Choice-compulsory study plan
2001/2002 (P2612) Electrical Engineering and Computer Science (3907V001) Electrical power Engineering P Czech Ostrava Choice-compulsory study plan
2001/2002 (P2612) Electrical Engineering and Computer Science (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner