457-0305/01 – Graph Theory (TG)

Gurantor department	Department of Applied Mathematics	Credits	4
Subject guarantor	doc. Mgr. Petr Kovář, Ph.D.	Subject version guarantor	doc. RNDr. Dalibor Fronček, CSc., Ph.D.
Study level	undergraduate or graduate	Requirement	Choice-compulsory
Year	2	Semester	summer
		Study language	Czech
Year of introduction	2003/2004	Year of cancellation	2009/2010
Intended for the faculties	FEI	Intended for study types	Follow-up Master

Extent of instruction for forms of study
Form of study	Way of compl.	Extent
Full-time	Credit and Examination	2+2
Part-time	Credit and Examination	2+2

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. Fronček: Úvod do teorie grafů, Slezská univerzita Opava, (1999). J. Matoušek, J. Nešetřil, Chapters in Discrete Mathematics, Karolinum Praha (2000).

Recommended literature:

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

Way of continuous check of knowledge in the course of semester

E-learning

Other requirements

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

1. Průměr, poloměr a obvod grafu. 2. Hranové grafy. Definice a konstrukce hranových grafů. Charakteristika hranových grafů. 3. Samokomplementární grafy. Komplement grafu. Vztah mezi průměrem grafu a jeho komplementem. Konstrukce nekonečných tříd samokomplementárních grafů. 4. Rozklady grafů. Rozklady kompletních grafů na izomorfní faktory. Rozklady grafů na faktory s danými průměry. Rozklady kompletních multiparitních grafů. 5. Problém rekonstrukce grafů. 6. Ramseyova teorie. Extremální teorie grafů. Ramseyova čísla. Zobecněná Ramseyova čísla. Další podobné problémy. 7. Grafy a grupy. Grupa amorfismu grafu. Grupa hranového automorfismu grafu. Cayleyho grafy. 8. Grafy s předepsaným okolím. Grafy s konstantním okolím. Extremální problémy. 9. Hypergrafy a designy. Hypergrafy, k uniformní hypergrafy. Designy. 10. Náhodné grafy. Enumerace grafů.

Conditions for subject completion

Full-time form (validity from: 1960/1961 Summer semester)

Task name	Type of task	Max. number of points (act. for subtasks)	Min. number of points	Max. počet pokusů
Exercises evaluation and Examination	Credit and Examination	100 (145)	51	3
Examination	Examination	100	0	3
Exercises evaluation	Credit	45	0	3

Mandatory attendence participation:

Show history

Conditions for subject completion and attendance at the exercises within ISP:

Show history

Occurrence in study plans

Academic year	Programme	Branch/spec.	Spec.	Zaměření	Form	Study language	Tut. centre	Year	W	S	Type of duty
2003/2004	(N2646) Information Technology	(1103T021) Computational Mathematics			P	Czech	Ostrava	2			Choice-compulsory	study plan
2003/2004	(N2646) Information Technology	(1103T021) Computational Mathematics			K	Czech	Ostrava	2			Choice-compulsory	study plan

Occurrence in special blocks

Block name	Academic year	Form of study	Study language	Year	W	S	Type of block	Block owner

Assessment of instruction

Předmět neobsahuje žádné hodnocení.