Cobertura de vértices

Ejemplos de coberturas de vértices (conformadas por los vértices en rojo).
Ejemplos de coberturas de vértices mínimas.

En la disciplina matemática de la teoría de grafos, una cobertura de vértices (en inglés, vertex cover) o simplemente cobertura de un grafo, es un conjunto de vértices tales que cada arista del grafo es incidente a al menos un vértice del conjunto.

El problema de encontrar la menor cobertura de vértices en un grafo se denomina problema de la cobertura de vértices. En teoría de la complejidad computacional se ha demostrado que este es un problema NP-completo.

La cobertura de vértices y aristas está muy relacionada con los conjuntos independientes y apareamientos o matchings.

Definición

Una cobertura de vértices para un grafo G es un conjunto de vértices V en los que cada arco de G incide al menos en un nodo de V. La cobertura de vértices mínima es la más pequeña de las coberturas de vértices. El número de cobertura de vértices para un grafo G es el tamaño de la cobertura de vértices mínima.

Ejemplos

  • Para cualquier grafo, el conjunto de todos sus vértices es trivialmente una cobertura de vértices.
  • Un grafo bipartito completo tiene y .

Propiedades

Véase también

Referencias

  • Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.

Read other articles:

Mutya Johanna Datul

Mutya Johanna DatulLahirMutya Johanna Fontiveros Datul17 April 1992 (umur 31)Santa Maria, Isabela, FilipinaTinggi5 ft 8 in (1,73 m)Pemenang kontes kecantikanGelarBinibining Pilipinas-Supranational 2013 Miss Supranational 2013AgensiBinibining Pilipinas CharitiesWarna rambutHitamWarna mataCokelat gelapKompetisiutamaMutya ng Pilipinas 2012(Top 10)Binibining Pilipinas 2013(Binibining Pilipinas-Supranational 2013)(Best in Evening Gown)(Binibining Photogenic)Miss Supranational ...

 

مقاطعة أورانج (كارولاينا الشمالية)

  لمعانٍ أخرى، طالع مقاطعة أورانج (توضيح). مقاطعة أورانج     الإحداثيات 36°04′N 79°07′W / 36.06°N 79.12°W / 36.06; -79.12  [1] تاريخ التأسيس 1752  سبب التسمية فيليم الخامس أمير أورانيا  تقسيم إداري  البلد الولايات المتحدة[2][3]  التقسيم الأعلى كارول�...

 

Vieillissement

Hans Baldung Grien : Les Âges et la Mort, c. 1540-1543. Le vieillissement est l'ensemble des modifications fonctionnelles diminuant progressivement l'aptitude d'un objet, d'une information ou d'un organisme à assurer ses fonctions dans le temps. Dans le cas d'un organisme vivant (être humain par exemple), la plupart des cellules et organes ont une durée de vie maximale génétiquement programmée, mais ce processus peut être accéléré par divers stress subis in utero ou durant la ...

French Future

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 Future – news · newspapers · books · scholar · JSTOR (January 2022) (Learn how and when to remove this template message) Political party in France French Future L'Avenir françaisAbbreviationLAFLeaderJean-Philippe TanguyFounded22 March 2021...

 

Красная книга Курской области

Красная книга Курской области Автор коллектив авторов Жанр региональнаякрасная книга Язык оригинала русский Оригинал издан 2017 Издатель Калининград, Курск Страниц 380 Носитель книга ISBN 978-5-9500671-8-1 Предыдущая 1 изд. (2001) Красная книга Курской области — аннотированный с...

 

Animals (Martin Garrix song)

2013 song by Martin Garrix AnimalsSingle by Martin Garrixfrom the EP Gold Skies Released17 June 2013 (2013-06-17)Recorded2013GenreBig room house[1]Length 5:04 (original mix) 2:56 (US radio edit) 2:45 (UK radio edit) Label Spinnin' Stmpd (2023 reissue)[2] Songwriter(s) Martijn Garritsen [3]Producer(s) Martin Garrix Martin Garrix singles chronology Just Some Loops (2013) Animals (2013) Wizard (2013) Alternative UK and US cover Music videoAnimals on YouTube...

ソー (オー＝ド＝セーヌ県)

Sceaux 行政国 フランス地域圏 (Région) イル＝ド＝フランス地域圏県 (département) オー＝ド＝セーヌ県郡 (arrondissement) アントニー郡小郡 (canton) 小郡庁所在地INSEEコード 92071郵便番号 92330市長（任期） フィリップ・ローラン（2008年-2014年）自治体間連合 (fr) メトロポール・デュ・グラン・パリ人口動態人口 19,679人（2007年）人口密度 5466人/km2住民の呼称 Scéens地理座標 北緯48度4...

 

Hillerød Municipality

Municipality in Hovedstaden, DenmarkHillerød Municipality Hillerød Kommune (Danish)Municipality Coat of armsCoordinates: 55°56′00″N 12°19′00″E / 55.933333333333°N 12.316666666667°E / 55.933333333333; 12.316666666667CountryDenmarkRegionHovedstadenEstablished1 January 2007SeatHillerødGovernment • MayorKirsten Jensen (A)Area • Total212.99 km2 (82.24 sq mi)Population (1. January 2023)[1] • ...

 

Fabrice Hadjadj

Pour les articles homonymes, voir Hadjadj. Fabrice HadjadjFabrice Hadjadj, à l'Institution Sainte-Jeanne d'Arc de Brignoles en 2009FonctionDirecteurPhilanthroposdepuis septembre 2012Yves SemenBiographieNaissance 15 septembre 1971 (52 ans)NanterreNationalité françaiseFormation Institut d'études politiques de ParisAgrégation de philosophieActivités Écrivain, philosophePère Bernard Hadjadj (d)Conjoint Siffreine Michel (d)Autres informationsDistinction Grand Prix catholique de litt�...

Guglielmo IV del Regno Unito

Guglielmo IV del Regno UnitoRitratto di re Guglielmo IV del Regno Unito di Martin Archer Shee, 1833, Castello di WindsorRe del Regno Unito di Gran Bretagna e IrlandaStemma In carica26 giugno 1830 –20 giugno 1837(6 anni e 359 giorni) Incoronazione8 settembre 1831 PredecessoreGiorgio IV SuccessoreVittoria Re di HannoverIn carica26 giugno 1830 –20 giugno 1837(6 anni e 359 giorni) PredecessoreGiorgio IV SuccessoreErnesto Augusto I Nome completoGuglielmo Enr...

 

Oscar I

Oscar I Porträtt av Oscar I från 1858. Kung av Sverige Regeringstid 8 mars 1844–8 juli 1859(15 år och 122 dagar) Kröning 28 september 1844 i Stockholm Företrädare Karl XIV Johan Efterträdare Karl XV Valspråk Rätt och sanning Kung av Norge Regeringstid 8 mars 1844–8 juli 1859(15 år och 122 dagar) Företrädare Karl III Johan Efterträdare Karl IV Valspråk Rätt och sanning Gemål Josefina av Leuchtenberg Barn Karl XVGustafOscar IIEugénieAugust Ätt Bernadotteska ätten Far Kar...

 

Portugal in the Eurovision Song Contest 2014

Eurovision Song Contest 2014Country PortugalNational selectionSelection processFestival da Canção 2014Selection date(s)Semi-final:8 March 2014Final:15 March 2014Selected entrantSuzySelected songQuero ser tuaSelected songwriter(s)EmanuelFinals performanceSemi-final resultFailed to qualify (11th)Portugal in the Eurovision Song Contest ◄2012 • 2014 • 2015► Portugal participated in the Eurovision Song Contest 2014 with the song Quero ser tua written b...

Clément XIII

Clément XIII Tableau peint par Anton Raphael Mengs. 1758. Pinacothèque nationale de Bologne. Biographie Nom de naissance Carlo Castelbarco Pindemonte della Torre di Rezzonico Naissance 7 mars 1693Venise, République de Venise Décès 2 février 1769 (à 75 ans)Rome, États pontificaux Pape de l'Église catholique Élection au pontificat 6 juillet 1758 (65 ans) Intronisation 16 juillet 1758 Fin du pontificat 2 février 176910 ans, 6 mois et 27 jours Benoît XIV Clément ...

 

迪奥斯达多·马卡帕加尔

迪奥斯达多·马卡帕加尔Diosdado Pangan Macapagal第9任菲律賓總統任期1961年12月30日—1965年12月30日前任卡洛斯·P·加西亚继任费迪南德·马科斯第6任菲律賓副總統任期1957年12月30日—1961年12月30日前任卡洛斯·P·加西亚继任伊曼纽尔·佩莱斯 个人资料出生(1910-09-28)1910年9月28日 美屬菲律賓馬尼拉逝世1997年4月21日(1997歲—04—21)（86歲） 菲律賓馬卡迪墓地 菲律賓馬卡迪達義市英...

 

格奥尔基·季米特洛夫

此條目之中立性有争议。其內容、語調可能帶有明顯的個人觀點或地方色彩。 (2011年6月)加上此模板的編輯者需在討論頁說明此文中立性有爭議的原因，以便讓各編輯者討論和改善。在編輯之前請務必察看讨论页。 格奥尔基·季米特洛夫保加利亚共产党中央委员会总书记任期1948年8月—1949年7月2日前任自己（第一书记）继任维尔科·契尔文科夫保加利亚共产党中央委员会第一�...

Stuart Taylor (footballer, born 1980)

For other people named Stuart Taylor, see Stuart Taylor (disambiguation). English footballer Stuart Taylor Taylor warming up for Aston Villa in 2008Personal informationFull name Stuart James Taylor[1]Date of birth (1980-11-28) 28 November 1980 (age 43)[2]Place of birth Romford, EnglandHeight 6 ft 6 in (1.98 m)[3]Position(s) GoalkeeperYouth career Wimbledon ArsenalSenior career*Years Team Apps (Gls)1997–2005 Arsenal 18 (0)1999 → Bristol Rovers (l...

 

Korea Independence Party

1928–1970 political party in South Korea Korea Independence Party 한국독립당韓國獨立黨FounderJo So-angFounded1928, in Shanghai, Republic of ChinaDissolved1970HeadquartersShanghai, Republic of China (1928–1945)Seoul, South Korea (from 1945)Armed wingKorean Independence ArmyIdeologyConservatism[1]Korean nationalism[1]Triequism[1]Hongik-Inganism[2][3]Factions:Social democracy[4]Political positionCentre-right to right-wingPolitics...

 

AXN Asia

AXN AsiaDiluncurkan21 September 1997JaringanSony Pictures TelevisionKC Global Media AsiaPemilikSony Pictures EntertainmentKC Global Media AsiaSloganAction RedefinedNegaraSingapuraKantor pusatSuntec City Mall, SingapuraSaluran seindukAnimax AsiaGEMONESitus webSitus web resmiTelevisi Internet4th MEDIA (Jepang)Channel 441 Logo AXN Asia hingga November 2015. Logo ini masih dipakai di India dan Asia Selatan. AXN Asia adalah saluran televisi berbayar yang dimiliki oleh Sony Pictures Entertainment d...

Superpuchar Polski 2014

Supercoppa di Polonia 2014Superpuchar Polski 2014 Competizione Supercoppa di Polonia Sport Calcio Edizione 23ª Organizzatore PZPN Date 9 luglio 2014 Luogo  Polonia Risultati Vincitore  Zawisza Bydgoszcz(1º titolo) Secondo  Legia Varsavia Cronologia della competizione 2012 2015 Manuale La 23ª edizione della Supercoppa di Polonia si è svolta il 9 luglio 2014 alla Pepsi Arena di Varsavia tra il Legia Varsavia, vincitrice del campionato e lo Zawisza Bydgoszcz, vincitore della ...

 

AlphaGo versus Lee Sedol

Artikel ini perlu dikembangkan agar dapat memenuhi kriteria sebagai entri Wikipedia.Bantulah untuk mengembangkan artikel ini. Jika tidak dikembangkan, artikel ini akan dihapus. Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: AlphaGo versus Lee Sedol – berita · surat ka...