گراف مکمل

گراف پترسن (در سمت چپ) و گراف مکمل آن (در سمت راست).

در نظریه گراف، مکمّل یا معکوس گراف G، گراف H با رئوس یکسان است به طوری‌که دو رأس متمایز H مجاورند اگر و فقط اگر آن دو راس در G مجاور نباشند. به این معنا که برای تولید مکمل یک گراف، تمام یال‌های غایب مورد نیاز برای تشکیل یک گراف کامل اضافه می‌شوند و تمام یال‌هایی که قبلاً وجود داشتند حذف می‌گردند.[۱]

تعریف

فرض کنید G = (V, E) یک گراف ساده باشد و K مجموعهٔ تمام زیرمجموعه‌های ۲-عضوی V است. در این صورت، H = (V, K \ E) گرافِ مکمّلِ گرافِ Gست،[۲] که در آن K \ E متمم نسبی E در K است. برای گراف‌های جهت‌دار، می‌توان مکمَل را به همین شکل تعریف کرد؛ یعنی به عنوان یک گراف جهت‌دار با مجموعه رئوس یک‌سان با استفاده از مجموعهٔ تمام زوج مرتب‌های ۲-عضوی از V به عنوان K در عبارت مذکور.

منابع

  1. ↑ Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, p. 6, ISBN 0-444-19451-7.
  2. ↑ Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6. Electronic edition, page 4.

Read other articles:

Forever (Charli XCX song)

2020 single by Charli XCX ForeverDesigned by Regards CoupablesSingle by Charli XCXfrom the album How I'm Feeling Now Released9 April 2020 (2020-04-09)Recorded6–8 April 2020[1]Genre Pop synth-pop psychedelic Length4:03LabelAtlanticSongwriter(s) Charlotte Aitchison Alexander Guy Cook BJ Burton Producer(s) A. G. Cook BJ Burton Charli XCX singles chronology Ringtone (remix) (2020) Forever (2020) Claws (2020) Audio videoForever on YouTube Forever is a song written and reco...

 

Гуров Олександр Васильович

У Вікіпедії є статті про інших людей із прізвищем Гуров. Гуров Олександр Васильович Народився 12 (24) травня 1845Російська імперіяПомер 8 жовтня 1920(1920-10-08) (75 років)Харків, Українська СРРПоховання Міське кладовище № 2Країна  Російська імперія Російська республіка Украї

 

Vyšné Valice

Vyšné Valice Felsővály Wappen Karte Vyšné Valice (Slowakei) Vyšné Valice Basisdaten Staat: Slowakei Slowakei Kraj: Banskobystrický kraj Okres: Rimavská Sobota Region: Gemer Fläche: 15,138 km² Einwohner: 253 (31. Dez. 2022) Bevölkerungsdichte: 17 Einwohner je km² Höhe: 230 m n.m. Postleitzahl: 982 52 (Postamt Kaloša) Telefonvorwahl: 0 47 Geographische Lage: 48° 28′ N, 20° 11′ O48.45888888888920.188888888889230Koordinaten: 48° 27′...

Нафтоналивний термінал

Нафтоналивни́й терміна́л (рос. нефтеналивной терминал; англ. oil loading terminal, нім. Rohölanlegestelle f, Rohölliegeplatz m) – комплекс споруд і пристроїв, призначених для підходу, швартування, стоянки і проведення вантажних операцій нафтоналивних суден (танкерів). Застарілий синонім – нафтон...

 

Petra Kronberger

Austrian alpine skier Petra KronbergerPersonal informationBorn (1969-02-21) 21 February 1969 (age 54)St. Johann im Pongau, AustriaOccupationAlpine skierHeight1.74 m (5 ft 9 in)Skiing careerDisciplinesSlalom, giant slalom, super-G, Downhill, combinedClubSC WerfenwengWorld Cup debut20 March 1987 (age 18)Retired28 December 1992 (age 23)OlympicsTeams2 – (1988, 1992)Medals2 (2 gold)World ChampionshipsTeams2 – (1989, 1991)Medals1 (1 gold)World CupSeasons6 – (1988–1993)Wi...

 

Stay Beautiful (The Last Goodnight song)

2008 single by The Last Goodnight Stay BeautifulSingle by The Last Goodnightfrom the album Poison Kiss B-sideNow That You're GoneReleasedFebruary 19, 2008[1]GenrePop rockLength3:14LabelVirginSongwriter(s) Kurtis John Jeff Blue Ely Weisfeld[2] Producer(s)Jeff Blue[2]The Last Goodnight singles chronology Pictures of You(2007) Stay Beautiful(2008) If I Talk to God(2008) Stay Beautiful is the second single from The Last Goodnight's album Poison Kiss (2007). Track listi...

Ramaiya Vastavaiya

2013 film by Prabhu Deva For the 2013 Telugu film, see Ramayya Vasthavayya. Ramaiya VastavaiyaTheatrical release posterDirected byPrabhu DevaWritten byAniket Shyamlal GuptaScreenplay byShiraz AhmedStory byVeeru PotlaBased onNuvvostanante Nenoddantana by PotlaProduced byKumar S. TauraniStarringGirish KumarShruti HaasanSonu SoodCinematographyKiran DeohansEdited byHemal KothariMusic bySongs:Sachin–JigarBackground Score:Sandeep ShirodkarProductioncompanyTips IndustriesDistributed byTips Industr...

 

Master's FA

Canadian semi-professional soccer club Football clubMaster's FutbolFull nameMaster's Futbol AcademyNickname(s)SaintsFounded2009; 14 years ago (2009)StadiumL'Amoreaux ParkScarborough, Toronto, OntarioOwnerJunior GrovesHead CoachGiuseppe Mattace-RasoLeagueLeague1 Ontario2021League1 Ontario, 19thPlayoffs: DNQWebsiteClub website Current season Master's Futbol Academy, commonly known as Master's FA, is a Canadian semi-professional soccer club based in Scarborough, Toronto, Ontari...

 

Escudo de El Carmen de Viboral

Escudo de Armas de El Carmen del Viboral[1]​ InformaciónEntidad Municipio de El Carmen de Viboral.Fecha de adopción 1961.Usos · Documentación oficial.· En la bandera que permanezca en el despacho del alcalde.· Pintado, esculpido o en placas en las fachadas de los edificios municipales.· Vehículos del parque automotor del municipio.· Folletos y cartelería.DescripciónLema Dios, Patria y Trabajo[editar datos en Wikidata] https://orientese.co/simbolos-de-el-carmen-de-vi...

Bowes-Lyon family

Scottish noble family Bowes-LyonParent houseClan LyonCountry United Kingdom  Scotland  England FounderJohn Lyon and Mary BowesCurrent headSimon Bowes-LyonTitles Earl of Strathmore and Kinghorne Lord of Glamis MembersQueen Elizabeth The Queen MotherPrincess Anne of DenmarkConnected familiesBritish royal familyDanish royal familyMottoIn Thee, O Lord, have I put my trust(Latin: In Te Domine Speravi)Estate(s)Glamis Castle (seat)Streatlam CastleGibside The Bowes-Lyon family descends...

 

Piala Liga Inggris 1998–1999

Piala Liga Inggris 1998–19991998–99 Football League CupNegara Inggris WalesTanggal penyelenggaraan11 Agustus 1998 s.d. 21 Maret 1999Jumlah peserta92Juara bertahanChelseaJuaraTottenham Hotspur(gelar ke-3)Tempat keduaLeicester CityPencetak gol terbanyakGianluca Vialli(6 gol)← 1997–1998 1999–2000 → Piala Liga Inggris 1998–1999 adalah edisi ke-39 penyelenggaraan Piala Liga Inggris, sebuah kompetisi dengan sistem gugur untuk 92 tim terbaik di Inggris. Edisi ini dimenangkan ...

 

Gangbuster (DC Comics)

Fictional character Comics character GangbusterGangbuster by Arthur Adams.Publication informationPublisherDC ComicsFirst appearanceAs Jose Delgado:Adventures of Superman #428(May 1987)As Gangbuster:Adventures of Superman #434(November 1987)Created byMarv Wolfman (writer) Jerry Ordway (artist)In-story informationAlter egoJose DelgadoTeam affiliationsS.T.A.R. LabsJustice LeagueSupporting character ofSupermanAbilitiesSkilled martial artist and gymnastCybernetic enhancement implants in his legs G...

A Beautiful Wife

2007 Italian filmA Beautiful WifeFilm posterItalianUna moglie bellissima Directed byLeonardo PieraccioniWritten byLeonardo PieraccioniGiovanni VeronesiStarringLeonardo PieraccioniLaura TorrisiCinematographyItalo PetriccioneEdited byStefano ChierchièMusic byGianluca SibaldiRelease date 14 December 2007 (2007-12-14) Running time93 minutesCountryItalyLanguageItalian A Beautiful Wife (Italian: Una moglie bellissima) is a 2007 Italian comedy film directed by Leonardo Pieraccioni.&#...

 

Sigrid discography

Sigrid discographySigrid performing at Oslo Spektrum in 2022Studio albums2Music videos11EPs3Singles17 The discography of Norwegian singer-songwriter Sigrid consists of two studio albums, three extended plays, 16 singles (including one as a featured artist), one guest appearance, eight promotional singles and 16 music videos. In addition to her own releases, Sigrid has also been a songwriter for other artists including Rudimental and Paloma Faith. On February 10, 2017 Sigrid released her debut...

 

马来西亚陆军

马来西亚陆军马来西亚陆军徽章存在時期1933年3月1日國家或地區 马来西亚效忠於 最高元首部門 马来西亚武装部队種類陆军功能地面作战駐軍／總部Tentera Darat Malaysia Kementerian Pertahanan Jalan Padang Tembak 50634 Kuala Lumpur別稱Gempur Wira冠名自国防部格言Gagah Setia（英勇忠诚）進行曲Gagah Setia指挥官現任指揮官丹斯里阿末哈斯布拉上将標識陆军军旗 马来西亚武装部队 马来西亚陆军 马...

The Lottery and Other Stories

The Lottery and Other Stories First edition coverAuthorShirley JacksonCountryUnited StatesLanguageEnglishGenreHorrorPublisherFarrar, Straus and CompanyPublication date1949Media typePrint (hardcover)Pages306 pp The Lottery and Other Stories is a 1949 short story collection by American author Shirley Jackson. Published by Farrar, Straus, it includes The Lottery and 24 other stories. This was the only collection of her stories to appear during her lifetime. Her later posthumous collections ...

 

PW-Sat

PW-Sat Заказчик Варшавский политехнический институт Оператор Польская академия наук Задачи Технологический спутник[1] Спутник Земли Стартовая площадка Куру Ракета-носитель Вега Запуск 13 февраля 2012[2] Сход с орбиты 28 октября 2014 COSPAR ID 2012-006G SCN 38083 Технические характер...

 

Ensign of the Russian Navy

You can help expand this article with text translated from the corresponding article in Russian. (November 2017) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia. Consider adding a topic to this template: there ar...

In the Heights

2005 musical by Lin-Manuel Miranda This article is about the stage musical. For the film adaptation, see In the Heights (film). For the film soundtrack, see In the Heights (soundtrack). In the HeightsBroadway promotional posterMusicLin-Manuel MirandaLyricsLin-Manuel MirandaBookQuiara Alegría Hudes ConceptLin-Manuel Miranda PremiereJuly 23, 2005: Eugene O'Neill Theater Center, Waterford, ConnecticutProductions2005 Waterford 2007 Off-Broadway2008 Broadway2009 US tour2015 West End2022 PolandAwa...

 

Kumamoto Suizenji Stadium

Kumamoto Suizenji StadiumLocation Kumamoto, Kumamoto, JapanOwnerKumamoto CityCapacity15,000Opened1960 Kumamoto Suizenji Stadium (熊本市水前寺競技場) is an athletic stadium in Kumamoto, Kumamoto, Japan. External links [1] vteRoasso KumamotoClub Players History All articles Stadium Egao Kenko Stadium Seasons 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 Former stadia Suizenji Stadium Rivalries Baka derby 32°47′38″N 130°44′29″E / þ...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!