K-INFO
HU
EN
Belépés
Tantárgy » BMEVISZA086
Régebbi verziók TAD letöltése (PDF)

Gráfelmélet

Graph Theory
A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
Tantárgy neve (magyarul, angolul)
Gráfelmélet
Graph Theory
Tantárgykód BMEVISZA086
Tantárgyjelleg —
Képzési szint —
Kurzustípusok és óraszámok (heti/féléves)
Kurzustípus elmélet gyakorlat laboratóriumi gyakorlat
óraszám (heti) 3 1 0
jelleg (kapcsolt/önálló) — kapcsolt —
Tanulmányi teljesítmény/értékelés típusa vizsga
Tantárgy kreditértéke 4
Tantárgyfelelős
Fleiner Tamás
beosztás: egyetemi tanár
Tantárgyat gondozó oktatási szervezeti egység
Számítástudományi és Információelméleti Tanszék
Kar Villamosmérnöki és Informatikai Kar
Tantárgy weboldala www.cs.bme.hu/....
Tantárgy elsődleges mintatantervi jellege —
Közvetlen előkövetelmények – Erős előkövetelmény nincs
Közvetlen előkövetelmények – Gyenge előkövetelmény nincs
Közvetlen előkövetelmények – Párhuzamos előkövetelmény nincs
Közvetlen előkövetelmények – Mérföldkő előkövetelmény nincs
Közvetlen előkövetelmények – Kizáró feltétel nincs

Célkitűzés

Tantárgyprogram
  1. Introduction

     

    Basic notions of graphs

 

    Why are they interesting and what are we interested in about them

 

    Trees and their main properties

 

    Coding and counting trees on n labelled vertices

 

2. The Königsberg bridges problem and Euler tours

 

          Euler tours in directed graphs

 

          The existence of deBruijn sequences

 

          Hamiltonian cycles

 

          The different nature of Hamiltonian cycles and Euler tours

 

          Necessary conditions for Hamiltonicity

 

          Sufficient conditions for Hamiltonicity due to Dirac, Pósa, Ore, and Chvátal

 

  1. Matchings and their relevance

     

          Necessary and sufficient conditions for the existence of a perfect matching in   bipartite graphs

 

          Kőnig's min-max theorem

 

          Perfect matchings in general graphs, Tutte's criterion

 

          Stable matchings and their use

 

    The existence of stable matchings in bipartite graphs

 

  1. Network flows

     

          The augmenting paths algorithm

 

          The Ford-Fulkerson min-max result and its relation to Kőnig's one

 

          Menger's min-max results

 

          The relevance of min-max formulae in general

 
  1. Planarity,

     

          Euler's formula and Kuratowski's criterion

 

          Minors and Wagner's criterion

 

          The equivalence of forbidding the Kuratowski graphs as minors and as topological    

 

          subgraphs

 

  1. Coloring graphs as a model for scheduling

     

           Bounding the chromatic number from above, greedy algorithm

 

           Bounding the chromatic number from below, Mycielski's construction

 

           Coloring edges

 

     Line graphs and the analogs of the previous bounds

 

     Improving the greedy algorithm, Vizing's upper bound

 
  1. Coloring planar graphs, 4-color theorem and 5-color theorem,

     

    Tait's result on the the relation of edge-coloring cubic planar graphs and the 4-color     

 

    theorem

 

    Perfect graphs, perfectness of bipartite graphs, their line graphs and the complements

 

    of these

 

    Odd holes, odd antiholes and their relevance

 

    Relation of complementation and perfectness in general

 

8. List coloring

 

    Relation of the list coloring number to the chromatic number, list coloring conjecture

 

    Galvin's theorem and its relation to stable matchings

 

          List coloring planar graphs

 

    Thomassen's inductive argument

 

    Voigt's construction for the sharpness of Thomassen's result

 
  1. Extremal graph theory

     

          Turán's sharp upper bound on the number of edges if the clique number is bounded

 

    The Erdős-Stone theorem and the Erdős-Simonovits limit result

 

          The Kővari-T.Sós-Turán upper bound for the analogous bipartite problem

 
  1. Ramsey theory

     

    Basic Ramsey-type results in graph theory

 

    Examples of Ramsey-type results outside graph theory

 

    Ramsey numbers, upper and lower bounds

 
  1. Hypergraphs as generalizations of graphs and as set systems

     

          Ramsey's result in the hypergraph setting

 

          Sperner systems and their maximum possible size

 

          LYM inequality

 

          Intersecting set systems, Erdős-Ko-Rado theorem

 
  1. Kneser's conjecture as a problem on hypergraphs

     

          Kneser graphs and their chromatic number, the Lovász-Kneser theorem

 

          Kneser graphs and fractional colorings

 

The objective of the first part of this course is to introduce the students with some of the most important notions of graph theory and develop their skill to solve basic exercises. It is also an objective of the course that on the way they become able to identify graph theory problems in a natural way even if those appear in a different setting.    The objective of the second part is to deepen the students' knowledge of graph theory by showing interrelations of some of the seemingly loosely related concepts and further develop their problem solving skills. Although there is no formal prerequisite for this course, some basic mathematical maturity is expected.   

Tanulmányi eredmények

Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:

Tudás

Nincsenek rögzített tanulási eredmények.

Képességek

Nincsenek rögzített tanulási eredmények.

Attitűd

Nincsenek rögzített tanulási eredmények.

Autonómia és felelősség

Nincsenek rögzített tanulási eredmények.

Oktatási módszertan

Lectures and recitations 

Tanulástámogató anyagok

Nincs megadva.

A tantárgy teljesítéséhez ajánlott előzetes ismeretek

Tudás típusú kompetenciák
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Képesség típusú kompetenciák
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
nincs
Általános szabályok

Nincs megadva általános szabály.

Teljesítményértékelési módszerek
Szorgalmi időszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Szorgalmi időszakban végzett teljesítményértékelések részaránya

Nincs megadva részarány.

Vizsgaidőszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Vizsgarészek részaránya

Nincs megadva részarány.

Érdemjegy megállapítása

Nincs megadva érdemjegy határ.

Jelenléti és részvételi követelmények

Nincs megadva jelenléti követelmény.

Javítás, ismétlés és pótlás különös szabályai

Nincs megadva.

Rövid leírás

Nincs megadva.

Részletes leírás

Nincs megadva.

Ajánlott tantárgyak

Nincs megadva.

A tantárgy elvégzéséhez szükséges tanulmányi munka

Nincs megadva munkaidő bontás.

Tantárgykövetelmények hatályossága
Tantárgykövetelmények hatályosságának kezdete:
—
Tantárgykövetelmények hatályosságának vége:
—
Tantervi elhelyezés

Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.