پاورپوینت مسائلی مشهور در گراف

پاورپوینت مسائلی مشهور در گراف (pptx) 15 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 15 اسلاید

قسمتی از متن PowerPoint (.pptx) :

به نام خداعنوان: مسائلی مشهور در گراف Vertex cover Min Vertex cover 𝛽(G) Matching Maximum matching ⍺’(G) Independent set Maximum independent set ⍺(G) Edge cover Maximum edge cover 𝛽’(G)  Kőnig's theorem 𝛽(G) = |V| -⍺(G) ⍺’(G)<= 𝛽(G) ⍺(G) = 𝛽’(G) In  bipartite graphs  Dénes Kőnig (1931) Augmenting path Berge's lemma States that a matching M in a graph G is maximum  if and only if there is no augmenting path  with M. Edmonds' algorithm   Jack Edmonds (1967) O(EV) O(E log V) Tarjan  f  f  f Hall’s theorem Gives a necessary and sufficient condition for being able to find matching in bipartite graphs that can cover at least one side of vertices. For each subset of X like S the N(S) is subset of Y that are all of the neighbors of S . We have |N(s)|>=|S|. The matching (blue edges) cover X * proof by induction or Berge lemma