Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 294)
Detail práce
  
Rozložitelnost grafů na souvislé podgrafy
Název práce v češtině: Rozložitelnost grafů na souvislé podgrafy
Název v anglickém jazyce: Decompositions of graphs into connected subgraphs
Klíčová slova: graf, podgraf, souvislost, rozklad, rozložitelnost
Klíčová slova anglicky: graph, subgraph, connectivity, edge-partitioning
Akademický rok vypsání: 2012/2013
Typ práce: diplomová práce
Jazyk práce: čeština
Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
Vedoucí / školitel: RNDr. Ondřej Pangrác, Ph.D.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 19.11.2012
Datum zadání: 20.11.2012
Datum potvrzení stud. oddělením: 27.11.2012
Datum a čas obhajoby: 15.09.2015 09:00
Datum odevzdání elektronické podoby:29.07.2015
Datum odevzdání tištěné podoby:31.07.2015
Datum proběhlé obhajoby: 15.09.2015
Oponenti: doc. RNDr. Jiří Fiala, Ph.D.
 
 
 
Zásady pro vypracování
Graf je rozložitelný, pokud pro každou $k$-tici kladných celých čísel $m_1,...,m_k$ takovou, že $m_1+...+m_k=m=|E|$ existuje rozklad hran na množiny $E_1,...,E_k$ a podgraf indukovaný hranami $E_i$ je souvislý pro $i=1,...,k$. Je známo, ža každý hranově $4$-souvislý graf je rozložitelný a na druhou stranu existuje příklad $2$-souvislého grafu, který rozložitelný není. Úkolem studenta je prozkoumat vliv různých grafových parametrů na rozložitelnost grafu, zejména se zaměřit na $3$-souvislé grafy.
Seznam odborné literatury
Matoušek, Nešetřil: Kapitoly z diskrétní matematiky. Karolinum 2007
Diestel: Graph Theory. Springer 2010
Barát, Thomassen: Dividing the edges of a graph into connected subgraphs of prescribed size. Eurocomb 2003
Předběžná náplň práce
Graf je rozložitelný, pokud pro každou $k$-tici kladných celých čísel $m_1,...,m_k$ takovou, že $m_1+...+m_k=m=|E|$ existuje rozklad hran na množiny $E_1,...,E_k$ a podgraf indukovaný hranami $E_i$ je souvislý pro $i=1,...,k$. Je známo, ža každý hranově $4$-souvislý graf je rozložitelný a na druhou stranu existuje příklad $2$-souvislého grafu, který rozložitelný není.
 
Univerzita Karlova | Informační systém UK