Домінівна множина

У теорії графів, домінівна множина для графа $G=(V,E)$ — така підмножина $D$ множини вершин $V,$ що кожна вершина не з $D$ є суміжною зі щонайменше однією вершиною з $D.$ Число домінування $\gamma (G)$ — число вершин у найменшій домінівній множині для $G.$

Задача домінівної множини займається дослідженням чи $\gamma (G)\leq K$ для певного графа $G$ і заданого $K;$ це класична NP-повна проблема вибору в теорії складності обчислень (Garey та Johnson, 1979). Отже вважають, що не існує алгоритму з поліноміальним часом виконання, який знаходить найменшу домінівну множину для заданого графа.

Зображення (a)–(c) праворуч, наводять три приклади домінівних множин на графі. У кожному прикладі, кожна біла вершина є суміжною хоча б з однією червоною вершиною, у такому випадку кажуть, що червоні вершини домінують над білими. Число домінування цього графа є 2: Приклади (b) і (c) показують, що існують домінівні множини з 2 вершинами, і можна перевірити, що для цього графа немає домінівної множини, що складається з 1 вершини.

Межі

Нехай $G$ буде графом з $n\geq 1$ вершин і нехай $\Delta$ буде найбільшим степенем графа. Тоді відомі такі обмеження на $\gamma (G)$ (Haynes, Hedetniemi та Slater, 1998a, Chapter 2):

Одна вершина може домінувати не більше ніж над $\Delta$ інших вершин; отже $\gamma (G)\geq n/(1+\Delta ).$
Множина всіх вершин є домінівною множиною для будь-якого графа; отже $\gamma (G)\leq n.$
Якщо $G$ не містить ізольованих вершин, тоді в $G$ існують дві неперетинні домінівні множини; докладніше дивись у доматичне число. Отже, в будь-якому графі без ізольованих вершин $\gamma (G)\leq n/2.$

Див. також

Домінівна множина ребер

Примітки

Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5, p. 190, problem GT2.
Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998a), Fundamentals of Domination in Graphs, Marcel Dekker, ISBN 0-8247-0033-3, OCLC 37903553.

Read other articles:

Bharatayuddha

Lihat pula: Mahabharata dan Perang Kurukshetra BharatayuddhaBagian dari Kakawin BharatayuddhaPertarungan Karna (kiri) melawan Arjuna, suatu adegan dari Bharatayuddha, dalam bentuk lukisan kaca Cirebon.LokasiKurusetra (Kurukshetra)Hasil dimenangkan pihak PandawaPihak terlibat Lima putra Pandu (Pandawa) dan sekutunya, dipimpin oleh Yudistira Seratus putra Dretarastra (Korawa) dan sekutunya, dipimpin oleh DuryodanaTokoh dan pemimpin YudistiraTrustajumena (Drestadyumna) † Resi Seta (Sweta)...

.br

.brDiperkenalkan18 April 1989Jenis TLDTLD kode negara InternetStatusAktifRegistriRegistro.brSponsorCGI.brPemakaian yang diinginkanEntitas yang berhubungan dengan BrasilPemakaian aktualSangat umum digunakan di BrasilDomain terdaftar4.837.316 (18 Agustus 2021)[1]PembatasanPembatasan yang berbeda-beda setiap subdomainnya.StrukturRegistasi dilakukan di tingkat ketigaDNSSECYaSitus webregistro.br.br adalah top-level domain kode negara Internet untuk Brasil. lbsRanah tingkat teratas ko...

Samson and Delilah (film 2009)

Samson and DelilahPoster rilis teatrikalSutradaraWarwick ThorntonProduserKath ShelperDitulis olehWarwick ThorntonPemeranRowan McNamaraMarissa GibsonSinematograferWarwick ThorntonPenyuntingRoland GalloisDistributorMadman EntertainmentTanggal rilis 20 Februari 2009 (2009-02-20) (Adelaide) 7 Mei 2009 (2009-05-07) (Australia) Durasi97 menitNegaraAustraliaBahasaInggrisWarlpiri Samson and Delilah adalah sebuah film Australia 2009 dan disutradarai oleh Warwick Thornton. Film terseb...

LGBT rights in Curaçao

LGBT rights in CuraçaoCuraçaoStatusLegalMilitaryYesDiscrimination protectionsDiscrimination based on heterosexual or homosexual orientation prohibitedFamily rightsRecognition of relationshipsSame-sex marriages performed in the Netherlands recognizedAdoptionNo Lesbian, gay, bisexual, and transgender (LGBT) people in Curaçao may face legal challenges not experienced by non-LGBT residents. Both male and female same-sex sexual activity are legal in Curaçao. Discrimination on the basis of het...

Suku Dani

Artikel ini bukan mengenai Suku Hubla. Orang HubulaHuwula, Dani, Parim, BalimSeorang lelaki Dani dengan dua buah taring babi yang menandakan bahwa ia seorang prajurit perangDaerah dengan populasi signifikanIndonesia: Papua Pegunungan Bahasabahasa DaniAgamaMayoritasProtestan & Katolik (95%) Minoritas(5%) yang beragama Islam, Animisme, Animatisme, Dinamisme dan TotemKelompok etnik terkaitHupla, Lani, Walak, Wano, Nduga Suku Dani atau Hubula adalah sekelompok suku yang mendiami wilayah Lemba...

Welcome 2 Life

Welcome 2 LifePoster promosiNama alternatifYou Only Live TwiceHangul웰컴2라이프 GenreFantasi[1]Komedi romantis[2]Ditulis olehYoo Hee-kyungSutradaraKim Geun-hongShim Soo-yeonPemeranJung Ji-hoonLim Ji-yeonKwak Si-yangNegara asalKorea SelatanBahasa asliKoreaJmlh. episode32ProduksiPengaturan kameraSingle-cameraDurasi35 menitRumah produksiKim Jong-hak Production[3]DistributorMunhwa Broadcasting CorporationRilis asliJaringanMBC TVFormat audioDolby DigitalRilis5 Agustus...

Bangkok–Nong Khai high-speed railway

Thai train service Bangkok–Nong Khai high-speed rail lineCRRC Fuxing Series EMU proposed for Northeastern high-speed rail line passenger services.OverviewOther name(s)Northeastern high-speed rail lineChina–Thailand railwayStatusUnder construction (Bangkok–Nakhon Ratchasima)LocaleThailandTerminiKrung Thep AphiwatNakhon Ratchasima (Phase 1)Nong Khai (Phase 2)Vientiane (Phase 3)Continues fromBoten–Vientiane railway (planned)ServiceTypeHigh-speed railOperator(s)State Railway of ThailandHi...

Человек прямоходящий

† Человек прямоходящий Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:Синапсиды�...

Hard (song)

2009 single by Rihanna HardSingle by Rihanna featuring Jeezyfrom the album Rated R ReleasedNovember 10, 2009 (2009-11-10)Recorded2009StudioStudios Devout (Paris, France); The Boom Boom Room (Burbank, California); Legacy Recording Studios (New York City, New York); Triangle Sound Studios (Atlanta, Georgia)GenreHip hopLength4:10Label Def Jam SRP Songwriter(s) Terius Nash Christopher Stewart Robyn Fenty Jay Jenkins Producer(s) Tricky Stewart The-Dream Rihanna singles chronolog...

Jack Albertson

American actor (1907–1981) Jack AlbertsonAlbertson in 1971BornHarold Albertson(1907 -06-16)June 16, 1907Malden, Massachusetts, U.S.DiedNovember 25, 1981(1981-11-25) (aged 74)Los Angeles, California, U.S.Other namesJohn AlbertsOccupationsActorcomediandancersingerYears active1926–1981Spouse June Wallace Thomson (m. 1952)Children1RelativesMabel Albertson (sister)George Englund (nephew) Harold Jack Albertson (June 16, 1907 – November 25,...

Шаблон:Мифология

МифологияРитуально-мифологическийкомплекс Система ценностей Сакральное Миф Мономиф Теория основного мифа Ритуал Обряд Праздник Жречество Мифологическое сознание Магическое мышление Низшая мифология Модель мира Цикличность Сотворение мира Мировое яйцо Мифическое �...

Новотитаровское сельское поселение

Сельское поселение России (МО 2-го уровня)Новотитаровское сельское поселение Флаг[d] Герб 45°14′09″ с. ш. 38°58′16″ в. д.HGЯO Страна Россия Субъект РФ Краснодарский край Район Динской Включает 4 населённых пункта Адм. центр Новотитаровская Глава сельского пос�...

乌克兰总理

烏克蘭總理Прем'єр-міністр України烏克蘭國徽現任杰尼斯·什米加尔自2020年3月4日任命者烏克蘭總統任期總統任命首任維托爾德·福金设立1991年11月后继职位無网站www.kmu.gov.ua/control/en/（英文）乌克兰乌克兰政府与政治系列条目宪法政府总统弗拉基米尔·泽连斯基總統辦公室国家安全与国防事务委员会总统代表（英语：Representatives of the President of Ukraine）总...

Orbital angular momentum multiplexing

Optical multiplexing technique Multiplexing Analog modulation AM FM PM QAM SM SSB Circuit mode(constant bandwidth) TDM FDM / WDM SDMA Polarization Spatial OAM Statistical multiplexing(variable bandwidth) Packet switching Dynamic TDMA FHSS DSSS OFDMA SC-FDM MC-SS Related topics Channel access methods Medium access control vte Orbital angular momentum multiplexing is a physical layer method for multiplexing signals carried on electromagnetic waves using the orbital angular momentum (OA...

French Upper Volta

French colony in West Africa (1919-58); now Burkina Faso 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: French Upper Volta – news · newspapers · books · scholar · JSTOR (August 2017) (Learn how and when to remove this message) Upper VoltaHaute-VoltaConstituent of French West Africa1919–19321947–1958 Fla...

Paul Salamunovich

American conductor (1927-2014) Paul Salamunovich conducting the St. Petersburg Philharmonic in Rome, Italy 2003 Paul Salamunovich KCSG (June 7, 1927 – April 3, 2014) was a Grammy-nominated, American conductor and educator. He was the Music Director of the Los Angeles Master Chorale from 1991 to 2001 and its Music Director Emeritus from 2001 until his death in 2014. He served as Director of Music at St. Charles Borromeo Church in North Hollywood, California, for 60 years between...

Tabrakan di udara Zagreb 1976

British Airways Penerbangan 476Inex-Adria Aviopromet Penerbangan 550Ringkasan kecelakaanTanggal10 September 1976RingkasanTabrakan di udara disebabkan oleh kelalaian ATCLokasiDekat Vrbovec, Yugoslavia 45°53′33″N 16°18′38″E / 45.89250°N 16.31056°E / 45.89250; 16.31056Total tewas176Total selamat0Pesawat pertamaG-AWZT, di Bandar Udara Charles de Gaulle kira-kira 3 bulan sebelum kecelakaanJenisHawker Siddeley Trident 3BOperatorBritish AirwaysRegistrasiG-AWZTAsal...

The Ramayana (Narayan book)

For a 1957 abridged retelling of the Ramayana in English by C. Rajagopalachari, see Ramayana (Rajagopalachari book). The Ramayana First editionAuthorR.K. NarayanLanguageEnglishGenreMythologyPublisherChatto and WindusPublication date1972Publication placeIndiaMedia typePrintISBN978-0-14-004428-7OCLC2798190Preceded byMy Days Followed byThe Painter of Signs The Ramayana is a mythological book by R. K. Narayan. It was first published by Chatto and Windus, London in 1972....

2006 Pendle Borough Council election

2006 UK local government election Main article: Pendle Borough Council elections Map of the results of the 2006 Pendle Borough Council election. Liberal Democrats in yellow, Conservatives in blue, Labour in red and British National Party in dark blue. Wards in dark grey were not contested in 2006. The 2006 Pendle Borough Council election took place on 4 May 2006 to elect members of Pendle Borough Council in Lancashire, England. One third of the council was up for election and the Liberal Demo...

Carlos Pachamé

Questa voce sugli argomenti allenatori di calcio argentini e calciatori argentini è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti dei progetti di riferimento 1, 2. Carlos PachaméPachamé nel Estudiantes LPNazionalità Argentina Altezza172 cm Peso73 kg Calcio RuoloAllenatore (ex centrocampista) CarrieraSquadre di club1 1963-1971 Estudiantes (LP)[1]1972-1973 Boca Juniors71 (2)1974-1976 Estudiantes (LP)27...

Ratomir Dujković

Danaraja, Margasari, Tegal

ويليام جيبسون (سياسي كندي)

Kenkichi Nishimi

Sunter Jaya, Tanjung Priok, Jakarta Utara

Hikayat Maharaja Ali

Pittsburg, Texas

Bid Zagh

Семейное право Австрии

Singapura cat

Federica Carta

Tatars