نمایش مبدأ برای گراف تام

[[Image:Paley9-perfect.svg|thumb|240px|گراف پالی از مرتبه ۹ که با سه رنگ، رنگ‌آمیزی شده و کلیک سه رأسی را نشان می‌دهد. در این گراف و هر کدام از زیرگراف‌های القایی آن، عدد رنگی برابر با عدد کلیکی است، لذا گراف تامی می‌باشد.]]
در [[نظریه گراف]]، '''گراف تام''' {{انگلیسی|Perfect Graph}}، گرافی است که [[رنگ‌آمیزی گراف|عدد رنگی]] آن برای هر [[زیرگراف القایی]] اش برابر با مرتبه بزرگترین [[کلیک (نظریه گراف)|کلیک]] آن [[زیرگراف]] (عدد کلیکی) باشد. به‌طور معادل می‌توان تعریف اخیر را برحسب نمادها بیان نماد: گراف دلخواهی چون <math>G=(V, E)</math> تام است اگر و تنها اگر برای تمام <math>S\subseteq V</math> داشته باشیم <math>\chi(G[S])=\omega(G[S])</math>.

گراف‌های تام شامل خانواده‌های مهم بسیاری از گراف‌ها بوده و موجب اتحاد و یکی شدن نتایج رنگ‌آمیزی‌ها و کلیک‌های مرتبط در آن خانواده‌ها می‌گردد. به عنوان مثال، در تمام گراف‌های تام، مسئله رنگ‌آمیزی گراف، مسئله کلیک ماکسیمم و [[مجموعه مستقل|مسئله مجموعه مستقل ماکسیمم]] را می‌توان به صورت [[زمان اجرای الگوریتم|زمان-چندجمله‌ای]] حل نمود. به علاوه، قضایای متعدد و مهم [[ترکیبیات|ترکیبیاتی]] از نوع مین-مکس، همچون [[قضیه دیلورث]] را می‌توان برحسب تام سازی گراف‌های خاصی بیان نمود.

== منابع ==
{{چپ‌چین}}
{{آغاز پانویس|2}}
* {{cite journal
  | author = Berge, Claude
  | author-link = Claude Berge
  | year = 1961
  | title = Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind
  | journal = Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math. -Natur. Reihe
  | volume = 10
  | pages = 114
  }}
* {{cite conference
  | author = Berge, Claude
  | author-link = Claude Berge
  | year = 1963
  | title = Perfect graphs
  | book-title = Six Papers on Graph Theory
  | publisher = Indian Statistical Institute
  | location = Calcutta
  | pages = 1–21}}
* {{cite journal
  |author1=Chudnovsky, Maria |author2-link=Gérard Cornuéjols |author2=Cornuéjols, Gérard |author3=Liu, Xinming |author4-link=Paul Seymour (mathematician) |author4=Seymour, Paul |author5=Vušković, Kristina|author5-link= Kristina Vušković
 | year = 2005
  | title = Recognizing Berge graphs
  | journal = Combinatorica
  | volume = 25
  | issue = 2
  | pages = 143–186
  | doi = 10.1007/s00493-005-0012-8
  |s2cid=2229369 |author1-link=Maria Chudnovsky }}
* {{cite journal
  |author1=Chudnovsky, Maria |author2-link=Neil Robertson (mathematician) |author2=Robertson, Neil |author3-link=Paul Seymour (mathematician) |author3=Seymour, Paul |author4-link=Robin Thomas (mathematician) |author4=Thomas, Robin
 | year = 2006
  | url = http://annals.princeton.edu/annals/2006/164-1/p02.xhtml
  | title = The strong perfect graph theorem
  | journal = [[Annals of Mathematics]]
  | volume = 164 | issue = 1
  | pages = 51–229
  | doi = 10.4007/annals.2006.164.51
  | arxiv = math/0212070
  |s2cid=119151552 |author1-link=Maria Chudnovsky }}
* {{cite journal
  | author = Gallai, Tibor
  | author-link = Tibor Gallai
  | title = Maximum-minimum Sätze über Graphen
  | year = 1958
  | journal = Acta Math. Acad. Sci. Hung.
  | volume = 9
  | issue = 3–4
  | pages = 395–434
  | doi = 10.1007/BF02020271
  | s2cid = 123953062
 }}
* {{Cite book
  | author = Golumbic, Martin Charles
  | author-link = Martin Charles Golumbic
  | title = Algorithmic Graph Theory and Perfect Graphs
  | publisher = Academic Press
  | year = 1980
  | isbn = 0-444-51530-5
  | url = http://www.elsevier.com/wps/find/bookdescription.cws_home/699916/description#description
  | access-date = 2007-11-21
  | archive-url = https://web.archive.org/web/20100522154759/http://www.elsevier.com/wps/find/bookdescription.cws_home/699916/description#description
  | archive-date = 2010-05-22
  | url-status = dead
  }} Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
* {{Cite book
 | last1 = Grötschel | first1 = Martin | author1-link = Martin Grötschel
 | first2 = László | last2 = Lovász | author-link2 = László Lovász
 | first3 = Alexander | last3 = Schrijver | author3-link = Alexander Schrijver
 | title = Geometric Algorithms and Combinatorial Optimization
 | publisher = Springer-Verlag
 | year = 1988
 }} See especially chapter 9, "Stable Sets in Graphs", pp. 273–303.
* {{cite journal
  | author = Lovász, László
  | author-link = László Lovász
  | year = 1972
  | title = Normal hypergraphs and the perfect graph conjecture
  | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
  | volume = 2
  | issue = 3
  | pages = 253–267
  | doi = 10.1016/0012-365X(72)90006-4
  }}
* {{cite journal
  | author = Lovász, László
  | author-link = László Lovász
  | year = 1972
  | title = A characterization of perfect graphs
  | journal = [[Journal of Combinatorial Theory]] | series = Series B
  | volume = 13
  | issue = 2
  | pages = 95–98
  | doi = 10.1016/0095-8956(72)90045-7
  }}
* {{cite conference
  | author = Lovász, László
  | author-link = László Lovász
  | year = 1983
  | title = Perfect graphs
  |editor1=Beineke, Lowell W. |editor2=Wilson, Robin J. | book-title = Selected Topics in Graph Theory, Vol. 2
  | pages = 55–87
  | publisher = Academic Press
  | isbn = 0-12-086202-6}}
{{پایان پانویس}}
{{پایان چپ‌چین}}
* {{یادکرد-ویکی|پیوند=https://en.wikipedia.org/w/index.php?title=Perfect_graph&oldid=1015007058|عنوان=Perfect Graph|زبان=انگلیسی|بازیابی=۲۹ مهٔ ۲۰۲۱}}

[[رده:گراف‌های تام]]