Đa thức màu

Trong lý thuyết đồ thị, Đa thức màu (tiếng Anh: Chromatic polynomial) của một đồ thị biểu diễn số cách tô màu các đỉnh của đồ thị đó theo số màu. Đa thức màu là đối tượng nghiên cứu của lý thuyết đại số đồ thị, một nhánh của toán học.

Đa thức màu được đề xuất bởi Geogre David Birkhoff trong một nỗ lực của ông nhằm giải quyết bài toán định lý bốn màu.

Lịch sử

Geogre David Birkhoff đưa ra khái niệm đa thức màu vào năm 1912. Lúc đó, nó chỉ được định nghĩa cho các đồ thị phẳng nhằm giải quyết bài toán định lý bốn màu, ý tưởng của Birkhoff như sau:

mọi đồ thị phẳng G đều có sắc số không lớn hơn 4, nếu $P(G,4)>0$ với mọi G, trong đó P(G,k) xác định số cách tô màu đỉnh G bởi k màu.

Vào năm 1932, Hassler Whitney đã mở rộng khái niệm đa thức màu cho đồ thị bất kì. Đến năm 1968, Read đặt câu hỏi: "liệu có tiêu chuẩn nào để xác định một đa thức cho trước có là đa thức màu hay không?". Câu hỏi này đến nay vẫn còn đang bị bỏ ngỏ. Chính vì vậy, người ta phải định nghĩa đa thức màu thông qua đồ thị.

Ngày nay, đa thức màu là đối tượng nghiên cứu trung tâm của lý thuyết đồ thị đại số.

Định nghĩa

Giá trị của đa thức màu của đồ thị G tại k bằng số cách tô màu đỉnh đồ thị G với k màu. Đa thức màu thường được ký hiệu là $P_{G}(k)$ , χ $_{G}(k)$ , hoặc π $_{G}(k)$ hoặc đôi khi là $P(G,k)$ .

Ví dụ:

Đồ thị đường đi $P_{3}$ có đa thức màu là:

P_{P_{3}}(k)=k\cdot (k-1)^{2}

Không thể tô màu đỉnh

P_{3}

chỉ với 0 hoặc 1 màu,

P_{P_{3}}(0)=P_{P_{3}}(1)=0

Có 2 cách tô màu đỉnh

P_{3}

bằng 2 màu,

P_{P_{3}}(2)=2

Có 12 cách tô màu đỉnh

P_{3}

bằng 3 màu,

P_{P_{3}}(3)=12

Sắc số có thể định nghĩa theo đa thức màu như sau:

sắc số của đồ thị G là giá trị nguyên dương nhỏ nhất k mà đa thức màu của G tại k nhận giá trị dương:

(G)=min{k:P_{G}(k)>0}

Ví dụ

Đa thức màu của một số đồ thị
Đồ thị tam giác $K_{3}$	$k(k-1)(k-2)$
Đồ thị đường đi $P_{n}$	$k(k-1)^{n-1}$
Đồ thị đầy đủ $K_{n}$	$k(k-1)(k-2)\dots (k-(n-1))$
Cây với $n$ đỉnh	$k(k-1)^{n-1}$
Đồ thị chu trình $C_{n}$	$(k-1)^{n}+(-1)^{n}(k-1)$
Đồ thị Petersen	$k(k-1)(k-2)(k^{7}-12k^{6}+67k^{5}-230k^{4}+529k^{3}-814k^{2}+775k-352)$

Xem thêm

Chú thích

Tham khảo

Liên kết ngoài

Read other articles:

Shivangi Joshi

Shivangi JoshiLahirShivangi Joshi18 Mei 1998 (umur 25)Pune, Maharashtra, IndiaKebangsaanIndianPekerjaanaktrisTahun aktif2013–sekarangDikenal atasYeh Rishta Kya Kehlata HaiKota asalDehradun, India Shivangi Joshi (lahir 18 Mei 1998)[1] adalah seorang aktris televisi India yang dikenal bermain sebagai Naira Goenka di Yeh Rishta Kya Kehlata Hai.[2][3] Kehidupan awal Joshi lahir di Pune, Maharashtra.[4] Dia bersekolah di kampung halamannya Dehradun...

Departemen Kerja Front Bersatu Tiongkok

Departemen Kerja Front Bersatu Komite Pusat Partai Komunis Tiongkok中共中央统一战线工作部Tanggal pendirian1942TipeLangsung melapor ke Komite Pusat Partai Komunis TiongkokKantor pusatJalan Fuyou 135, Distrik Xicheng, BeijingLokasiBeijingKetuaYou QuanWakil ketua eksekutifZhang YijiongWakil ketuaBagatur, Xu Lejiang*, Shi Dagang, Ran Wanxiang, Dai JunliangSekretaris DisiplinSu BoOrganisasi indukKomite Pusat Partai Komunis TiongkokSitus webwww.zytzb.gov.cn*Tingkat kementerian Departemen...

Холокост на Украине

Часть серии статей о Холокосте Идеология и политика Расовая гигиена · Расовый антисемитизм · Нацистская расовая политика · Нюрнбергские расовые законы Шоа Лагеря смерти Белжец · Дахау · Майданек · Малый Тростенец · Маутхаузен ·&...

Yesterday (film 2004)

YesterdayPoster film YesterdaySutradaraDarrell RoodtProduserAnant SinghHelena SpringDitulis olehDarrell RoodtPemeranLeleti KhumaloHarriet LenabeDistributorHBO Films (AS)Tanggal rilis 3 September 2004 (2004-09-03) Durasi96 menitNegaraAfrika SelatanBahasaZulu Yesterday adalah sebuah film Afrika Selatan 2004 yang ditulis dan disutradarai oleh Darrell Roodt. Film tersebut dinominasikan pada kategori Film Berbahasa Asing Terbaik di Academy Awards ke-77. Film tersebut juga memenangkan Suara Te...

Playboy

Pour les articles homonymes, voir Playboy (homonymie). Playboy Logo de Playboy. Pays États-Unis Langue anglais Périodicité mensuel Genre presse masculine érotique Diffusion 1 500 000 ex. (2011) Fondateur Hugh Hefner Date de fondation décembre 1953 à Chicago Date du dernier numéro printemps 2020 Éditeur Playboy Enterprises ISSN 0032-1478 Site web playboy.com modifier Playboy est un magazine de la presse masculine américain fondé à Chicago en 1953 par Hugh Hefner[1]....

Alameda County Library

Public library system in California's Alameda County This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article contains content that is written like an advertisement. Please help improve it by removing promotional content and inappropriate external links, and by adding encyclopedic content written from a neutral point of view. (July 2022) (Learn how and when to remove this template mes...

St. Joseph's Roman Catholic Church (Providence, Rhode Island)

Historic church in Rhode Island, United States United States historic placeSt. Joseph's Roman Catholic ChurchU.S. National Register of Historic Places Show map of Rhode IslandShow map of the United StatesLocationProvidence, Rhode IslandCoordinates41°49′17″N 71°23′50″W / 41.82139°N 71.39722°W / 41.82139; -71.39722Built1851ArchitectPatrick C. KeelyArchitectural styleGothicWebsitehttps://stjosephprovidence.orgNRHP reference No.74000004 [1 ...

2007 Boston College Eagles football team

American college football season 2007 Boston College Eagles footballACC Atlantic Division championChamps Sports Bowl championACC Championship Game, L 16–30 vs. Virginia TechChamps Sports Bowl, W 24–21 vs. Michigan StateConferenceAtlantic Coast ConferenceDivisionAtlantic DivisionRankingCoachesNo. 11APNo. 10Record11–3 (6–2 ACC)Head coachJeff Jagodzinski (1st season)Offensive coordinatorSteve Logan (1st season)Defensive coordinatorFrank Spaziani (9th season)Capta...

Конвенция о рабстве

Конвенция о рабстве 1926 года Тип договора Конвенция Дата подписания 25 сентября 1926 года Место подписания Женева Вступление в силу 9 марта 1927 года Стороны 99 Место хранения Дворец Наций, Женева Языки Английский, французский Текст в Викитеке Конвенция о рабстве 1926 года...

Unione Sportiva Lucchese Libertas 1947-1948

Voce principale: Associazione Sportiva Lucchese Libertas 1905. Unione Sportiva Lucchese LibertasStagione 1947-1948Sport calcio Squadra Lucchese Allenatore Árpád Hajós, poi dalla 8ª Giulio Cappelli, poi dalla 29ª Tony Cargnelli Presidente Antonio Fontana Serie A16º posto Maggiori presenzeCampionato: Mezzadri (37) Miglior marcatoreCampionato: Conti (19) 1946-1947 1948-1949 Si invita a seguire il modello di voce Questa voce raccoglie le informazioni riguardanti il l'Unione Sportiva L...

Chuck steak

Cut of beef Chuck steakDifferent U.S. cuts of beefTypecut of beef Part of a series onSteak Main articles Steak Beefsteak Fish steak Pork steak Steakhouse List of steak dishes Asado Beef Manhattan Beef Wellington Bife a cavalo Bistecca alla fiorentina Boiled beef Bulgogi Carpetbag steak Carne asada Chateaubriand steak Cheesesteak Chicken fried steak Bistek Tagalog Bollito misto Delmonico steak Fajita Finger steaks Hamburg steak London broil Mongolian beef Pepper steak Pot roast Roast beef Ital...

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。概要壱万円日本銀行券（「壱」が大字）弐千円日本銀行券（「弐」が大字）漢数字には「一」「二」「三」と続く小字と、「壱」「�...

Hyde Park (New York)

Pour les articles homonymes, voir Hyde Park (homonymie). Cet article est une ébauche concernant une localité de l’État de New York. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Hyde Park Administration Pays États-Unis État New York Démographie Population 20 851 hab. (2000) Densité 202 hab./km2 Géographie Coordonnées 41° 47′ 28″ nord, 73° 54′ 27″...

约翰斯顿环礁

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌：《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

2020年夏季奥林匹克运动会马来西亚代表团

2020年夏季奥林匹克运动会马来西亚代表團马来西亚国旗IOC編碼MASNOC马来西亚奥林匹克理事会網站olympic.org.my（英文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員30參賽項目10个大项旗手开幕式：李梓嘉和吳柳螢（羽毛球）[1][2]閉幕式：潘德莉拉（跳水）[3]獎牌榜排名第74 金牌銀牌銅�...

Daggett County, Utah

County in Utah, United States County in UtahDaggett CountyCountyDaggett County Courthouse in Manila, May 2008Location within the U.S. state of UtahUtah's location within the U.S.Coordinates: 40°53′N 109°31′W / 40.89°N 109.51°W / 40.89; -109.51Country United StatesState UtahFoundedJanuary 7, 1918Named forEllsworth DaggettSeatManilaLargest townManilaArea • Total721 sq mi (1,870 km2) • Land697 sq mi (1,810...

غودزيلا

هذه المقالة عن غودزيلا، شخصية خيالية. لمعانٍ أخرى، طالع غودزيلا (توضيح). غودزيلا غودزيلا في لقطة من الفيلم الأصلي. معلومات شخصية الحياة العملية أول ظهور غودزيلا (فيلم 1954) آخر ظهور غودزيلا ضد كونغ (2020) المبتكر إيجي تسوبورايا النوع كايجو الجوائز نجمة على ممر الشهرة في هو...

Asociación de Scouts de Bolivia

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Asociación de Scouts de Bolivia – news · newspapers · books · scholar · JSTOR (February 2010) (Learn how and when to remove this message) Asociación de Scouts de BoliviaHeadquarterscalle litoral #300, CochabambaCountryBoliviaFounded1911Membership7,898Affiliat...

Native American Church

Native American religion Not to be confused with Neo-American Church. Native American ChurchNative American Church's symbolTypeSyncretic, religious syncreticClassificationNative AmericanFounderQuanah Parker[1]Origin19th century United StatesSeparationsBig moon peyotismMembers250,000 Part of a series onPsychedelia Arts Psychedelic art Algorithmic art Cyberdelic Diffraction Fractal art Liquid light show LSD art Paisley Phosphene Psychedelic music Acid house Acid jazz Acid rock Acid tech...

Niskanen Center

American moderate think tank founded in 2015 Niskanen CenterFormation2015; 9 years ago (2015)[1]HeadquartersWashington, D.C., U.S.PresidentTed GayerRevenue (2021) $4,639,471[2]Expenses (2021)$4,639,471[2]WebsiteNiskanenCenter.org The Niskanen Center is an American think tank based in Washington, D.C. that advocates environmentalism, immigration reform, civil liberties, and strengthening social insurance around market-oriented principles.[1] ...