Csúcsgráf

Egy csúcsgráf – a piros csúcs eltávolításával kapott részgráf síkba rajzolható.

A matematika, azon belül a gráfelmélet területén egy csúcsgráf (apex graph) olyan gráf, ami egyetlen csúcs eltávolításával síkbarajzolhatóvá tehető. A törölt csúcs a gráf csúcspontja (apex). A csúcsgráfnak több csúcspontja is lehet, például a K5 és K3,3 minimális nem síkbarajzolható gráfok minden csúcsa csúcspont. A nullgráfot szintén csúcsgráfnak szokás tekinteni, bár nincs benne eltávolítható csúcs.

A csúcsgráfok a minorképzés műveletére zártak, és a gráfminor-elméletben többfelé előkerülnek: a láncmentes beágyazás,[1] Hadwiger-sejtés,[2] YΔY-redukálható gráfok,[3] illetve a faszélesség és átmérő közti kapcsolat esetében.[4]

Jellemzés és felismerés

A csúcsgráfok a minorképzés műveletére zártak: egy csúcsgráf bármelyik élének összehúzásával, bármelyik él vagy csúcs eltávolításával egy másik csúcsgráfhoz jutunk. Tehát ha G egy csúcsgráf, melynek csúcspontja v, akkor bármely, v-t nem érintő összehúzás vagy eltávolítás megőrzi a maradék gráf síkba rajzolhatóságát, ahogy egy v-vel érintkező él eltávolítása is. Ha egy v-vel érintkező él összehúzásra kerül, a maradék gráffal ugyanaz történik, mintha az él másik végpontját eltávolítanánk. És ha magát v-t távolítjuk el, bármely másik csúcsot kinevezhetjük csúcspontnak.[5]

A Robertson–Seymour-tétel alapján, mivel minorzárt gráfcsaládot alkotnak, a csúcsgráfok rendelkeznek tiltott minor-alapú osztályozással. Tehát csak véges sok olyan gráf létezik, ami nem csúcsgráf és nem tartalmaz másik nem-csúcsgráfot minorként. Ezeket a gráfokat nevezik a csúcsgráfok tiltott minorainak (obstrukcióhalmazának). Bármely G gráf akkor csúcsgráf, ha nem nem tartalmazza minorként valamelyik tiltott minort. Az obstrukcióhalmaz elemei közé tartozik a Petersen-gráfcsalád hét gráfja, három nem összefüggő gráf, ami két K5 és egy K3,3 közül kettő-kettőnek a diszjunkt uniójából származik, és több másik gráf. A tiltott minorok teljes listáját azonban még nem sikerült összeállítani, 2016-ban 263 ilyen gráf volt ismert.[5][6]

Bár a tiltott minorok listája még nem teljes, annak tesztelése, hogy adott gráf csúcsgráf-e, lineáris időben megoldható. Általánosabban, bármely rögzített k konstansra, lineáris időben felismerhetők az ún. k-csúcsgráfok, azaz a gráfok, melyekből jól megválasztott legfeljebb k csúcs eltávolításával síkbarajzolható gráfhoz jutunk.[7] Ha azonban k változó, a probléma NP-teljes.[8]

Kromatikus szám

Egy csúcsgráf kromatikus száma legfeljebb öt lehet: a síkbarajzolható alapgráf kromatikus száma a négyszíntétel alapján legfeljebb négy, a maradék egy csúcsponthoz pedig legfeljebb egy új színre van szükség. (Robertson, Seymour & Thomas 1993a) ennek a ténynek a felhasználásával bizonyították a Hadwiger-sejtés k = 6 esetét, miszerint minden 6-kromatikus gráf tartalmazza a K6 teljes gráfot minorként: megmutatták, hogy bármely minimális ellenpéldának csúcsgráfnak kellene lennie, de mert 6-kromatikus csúcsgráf nem létezik, így az ellenpélda sem.

A matematika megoldatlan problémája:
Minden 6-szorosan csúcsösszefüggő, -minormentes gráf csúcsgráf?
(A matematika további megoldatlan problémái)

(Jørgensen 1994) sejtése szerint minden 6-szorosan csúcsösszefüggő gráf csúcsgráf, ha nem tartalmazza a K6-t minorként. Ha ezt sikerülne bizonyítani, abból a Hadwiger-sejtés korábban említett Robertson–Seymour–Thomas-féle eredménye is azonnal következne.[2] A Jørgensen-sejtés egyelőre bizonyítatlan,[9] ha azonban hamis, csak véges sok ellenpéldája létezhet.[10]

Helyi faszélesség

Egy F gráfcsaládnak akkor van korlátos helyi faszélessége (bounded local treewidth), illetve rendelkezik az átmérő-faszélesség tulajdonsággal (diameter-treewidth property), ha a család gráfjainak faszélességét felülről korlátozza átmérőjük egy függvénye, tehát ha létezik olyan ƒ függvény, hogy egy F-beli, d átmérőjű gráf faszélessége legfeljebb ƒ(d). A csúcsgráfok nem rendelkeznek korlátos helyi faszélességgel: az n × n-es rácsgráf minden csúcsának a csúcsponttal való összekötésével kapott csúcsgráf faszélessége n, átmérője pedig 2, tehát a faszélesség nem lehet az átmérő függvénye által korlátozva. A csúcsgráfok családjának mégis köze van a korlátos helyi faszélességhez: a minorzárt F gráfcsaládnak pontosan akkor van korlátos helyi faszélességgel, ha az obstrukciós halmazában legalább egy csúcsgráf szerepel, azaz csúcsgráfminor-mentes.[4] Tehát a csúcsgráfminor-mentes gráfcsaládok megegyeznek a korlátos helyi faszélességű minorzárt gráfcsaládokkal.

Az átmérő-faszélesség tulajdonság közeli kapcsolatban áll a bidimenzionalitás algoritmikus elméletével, és a csúcsgráfminor-mentes gráfok számos algoritmikus problémája megoldható polinom időben, vagy rögzített paraméter mellett kezelhető, vagy polinomiális approximációs sémával közelíthető.[11] A csúcsgráfminor-mentes gráfokra a gráfminor-tétel egy erősebb változata alkalmazható, ami a gráfszínezési és utazó ügynök-problémák további approximációs algoritmusaihoz vezet.[12] Ezeknek az eredményeknek némelyike kiterjeszthető tetszőleges minorzárt gráfcsaládokra az őket a csúcsgráfminor-mentes gráfokkal kapcsolatba hozó strukturális tételek segítségével.[13]

Beágyazások

Ha G csúcsgráfban v csúcspont és τ megegyezik G\{v} egy síkba rajzolásában a v összes szomszédjának lefedéséhez szükséges tartományok minimális számával, akkor G beágyazható egy τ − 1 génuszú kétdimenzós felületbe: egyszerűen hozzá kell adni a hidak ezen számát a síkba ágyazáshoz, amik összekötik azokat a tartományokat, melyekbe v bekötendő. Például egy külsíkgráfhoz (melynél τ = 1) egyetlen csúcsot adva síkbarajzolható gráfot kapunk. Ha G\{v} 3-szorosan összefüggő, akkor a génuszra vonatkozó korlát az optimálisnak konstansszorosa: G minden felületbe ágyazása legalább τ/160-as génuszt igényel. A csúcsgráf felületbe ágyazása optimális génuszának megállapítása azonban NP-nehéz.[14]

Egy csúcsgráf síkbarajzolható részének lehetséges beágyazásait SPQR-fákkal kódolva ki lehet számítani a gráf olyan lerajzolását, melyben a metsző élek csak a csúcspont összefüggésében jönnek létre, így minimalizálva a metsző élek számát polinom idő alatt.[15] Ha azonban tetszőleges metszést megengedünk, NP-nehéz feladat a metsző élek számának minimalizálása, még azon speciális csúcsgráfoknál is, melyek egy síkbarajzolható gráfhoz egyetlen él hozzáadásával jöttek létre.[16]

A csúcsgráfok láncmentesen beágyazhatók a háromdimenziós térbe: beágyazhatók oly módon, hogy a gráf minden köre egy körlemez határán legyen, melyen a gráf más eleme nem hatol át.[17] Egy ilyen beágyazás megkapható a gráf síkbarajzolható részének síkba rajzolásával, majd a csúcspont a sík fölé helyezésével és a csúcspont a szomszédaival való egyenes vonalú összekötésével. A láncmentesen beágyazható gráfok minorzárt családot alkotnak, melynek minimális tiltott minorai a Petersen-gráfcsalád;[1] így ezek a gráfok a csúcsgráfok tiltott minorai is egyben. Léteznek azonban láncmentesen beágyazható gráfok, melyek nem csúcsgráfok.

YΔY-redukálhatóság

Robertson példája nem YΔY-redukálható csúcsgráfra.

Egy összefüggő gráf akkor YΔY-redukálható, ha a lépések egy sorozatával egyetlen csúcsra redukálható, ahol a lépések a következők lehetnek: Δ-Y vagy Y-Δ átalakítás, egy hurokél vagy többszörös él átalakítása, egyetlen szomszéddal rendelkező csúcs eltávolítása, kettő fokszámú csúcs és a belőle kiinduló élek cseréje egyetlen élre.[3]

A csúcsgráfokhoz és a láncmentesen beágyazható gráfokhoz hasonlóan a YΔY-redukálható gráfok is zártak a minorképzés műveletére nézve. A láncmentesen beágyazható gráfokhoz hasonlóan az obstrukciós halmazukhoz tartozik a Petersen-gráfcsalád hét gráfja, mint tiltott minor, ami felvetette a kérdést, hogy vajon a két gráfcsalád megegyezik-e. Neil Robertson talált olyan csúcsgráfot, ami nem YΔY-redukálható, ezért az YΔY-redukálható gráfok obstrukciós halmazába további gráfoknak kell tartozniuk.[3]

Az ábrán látható Robertson csúcsgráfja. A gráf előállítható akár egy rombododekaéder három fokszámú csúcsaihoz egy csúcspont hozzáadásával, vagy egy négydimenziós hiperkockagráf két átlósan szemközt lévő csúcsának összeolvasztásával. Mivel a rombododekaéder gráfja síkba rajzolható, a Robertson-féle gráf csúcsgráf. Háromszögmentes gráf, melynek minimális fokszáma négy, ezért az YΔY-redukciók nem változtathatják meg.[3]

Csaknem síkbarajzolható gráfok

A 16 csúcsú Möbius-létra, a csaknem síkbarajzolható gráfok egy példánya.

Egy csúcsgráfnak nem feltétlenül van egyetlen kijelölt csúcspontja. Például a minor-minimális nem síkbarajzolható gráfokban – a K5-ben és a K3,3-ban – bármely csúcs kiválasztható csúcspontként. Wagner (1967, 1970) definíciója szerint egy csaknem síkbarajzolható gráf (nearly planar graph) olyan, nem síkbarajzolható csúcsgráf, melyben bármelyik csúcs kiválasztható csúcspontként; tehát például a K5 és K3,3 csaknem síkbarajzolható. Elvégezte az ilyen gráfok osztályozását, négy részhalmazba osztva őket, melyek egyike azokból a gráfokból áll, melyek (a Möbius-létrákhoz hasonlóan) beágyazhatók a Möbius-szalagba úgy, hogy a szalag éle egybeesik a gráf egy Hamilton-körével. A négyszíntétel bizonyítása előtt sikerült bizonyítania, hogy a csaknem síkbarajzolható gráfok legfeljebb négy színnel színezhetők, kivéve a páratlan külső körrel rendelkező gráfokat, melyek egy kerékgráfból jönnek létre a központi csúcs két egymás melletti csúcsra való kicserélésével, melyekhez öt színre van szükség. Ráadásként bizonyította, hogy a kocka nyolc csúcsú komplementere kivételével az összes csaknem síkbarajzolható gráfnak létezik a projektív síkba való beágyazása.

Maga a „csaknem síkbarajzolható gráf” kifejezés erősen kétértelmű: használták már a csúcsgráfokra,[18] a síkbarajzolható gráfokhoz egy él hozzáadásával kapott gráfokra,[19] síkba rajzolt gráfok egyes tartományainak korlátos útszélességű „vortex”-ekre lecserélésével kapott gráfokra [20] és néhány más, kevésbé precízen definiált gráfcsaládra is.

Kapcsolódó gráfcsaládok

Egy gráf akkor k-csúcsgráf, ha k vagy kevesebb csúcs eltávolítása után síkbarajzolható lesz. Az 1-csúcsgráf fogalma megegyezik a csúcsgráféval.

(Max & Mackall 2016) szerint egy gráf él-csúcsgráf, ha van olyan éle, melynek eltávolításával a gráf síkbarajzolható lesz, továbbá egy gráf összehúzás-csúcsgráf, ha van olyan éle, melynek összehúzásával a gráf síkbarajzolható lesz.

Kapcsolódó szócikkek

  • Poliéder-hasáb (polyhedral pyramid), egy 4-dimenziós politóp, aminek csúcsai és élei olyan csúcsgráfot alkotnak, melyben a csúcs egy poliédergráf minden csúcsával szomszédos

Jegyzetek

Read other articles:

1st Philippine LegislatureOctober 16, 1907 – May 20, 1909Governor-General James Francis SmithCommissionMembers12AssemblySpeakerSergio Osmeña (Nacionalista)Majority leaderManuel L. Quezon (Nacionalista)Minority leaderVicente Singson Encarnacion (Progresista)Members812nd Philippine Legislature (1909) ► Politics of the Philippines Government Constitution of the Philippines Charter Change Laws Legal codes Taxation Executive President of the Philippines Bongbong Marcos (PFP) Vice...

 

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 relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: Closer novel – news · newspapers · books · scholar · JSTOR (November 2012) (Learn how and when to remove this template message) This article's plot ...

 

Awards of the Japanese AcademyNippon Akademī-shō Statuetta del 2012 (premio alla miglior regia, conferito a Izuru Narushima per il film Yōkame no semi (八日目の蟬?)) LuogoGiappone Anni1978 - oggi Fondato daJapanese Academy Awards Association (日本アカデミー賞協会 Nippon Akademī-shō kyōkai?)) Datemarzo Generecinema Sito ufficialewww.japan-academy-prize.jp/ Modifica dati su Wikidata · Manuale Gli Awards of the Japanese Academy (日本アカデミー賞 Nippon ...

Артем Фаворов Особисті дані Повне ім'я Артем Володимирович Фаворов Народження 19 березня 1994(1994-03-19) (29 років)   Київ, Україна Зріст 185 см Вага 75 кг Громадянство  Україна Позиція півзахисник Інформація про клуб Поточний клуб «Академія Пушкаша» Номер 19 Юнацькі клуби...

 

Kraftwerk Aschach Das Kraftwerk von stromabwärts Das Kraftwerk von stromabwärts Lage Kraftwerk Aschach (Oberösterreich) Koordinaten 48° 23′ 6″ N, 14° 1′ 21″ O48.38514.0225280Koordinaten: 48° 23′ 6″ N, 14° 1′ 21″ O Land Osterreich Österreich Oberosterreich Oberösterreich Ort Aschach an der Donau Gewässer Donau Gewässerkilometer km 2162,67 Höhe Oberwasser 280 m ü. A. Kraftwerk Eigen...

 

Surf Bungaku KamakuraAlbum studio karya Asian Kung-Fu GenerationDirilis5 November 2008Direkam2006-2008GenreIndie rock, alternative rock, surf rockDurasi31:27LabelKi/oon RecordsKSCL-1310ProduserAsian Kung-Fu GenerationKronologi Asian Kung-Fu Generation Mada Minu Ashita ni(2008)Mada Minu Ashita ni2008 Surf Bungaku Kamakura(2008) Magic Disk(2010)Magic Disk2010 Penilaian profesional Skor ulasan Sumber Nilai Allmusic [1] The Japan Times (baik)[2] Surf Bungaku Kamakura (サーフ

Stasiun Minami-Pippu (南比布駅 Minami-Pippu-eki) adalah sebuah stasiun kereta api yang berada di Jalur Utama Sōya terletak di 1 Sen-5 Minami, Pippu, Subprefektur Kamikawa, Hokkaido, Jepang, yang dioperasikan oleh JR Hokkaido. Stasiun ini diberi nomor W33. Stasiun Minami-Pippu南比布駅Tampilan penuh Stasiun Minami-Pippu, Agustus 2020Lokasi1 Sen-5 Minami, Pippu, Kamikawa-gun, Hokkaido 078-0311, JepangJepangKoordinat43°51′12.5″N 142°28′2″E / 43.853472°N 142.46722

 

Сурхандар'я 37°12′16″ пн. ш. 67°18′38″ сх. д. / 37.20470000002777766° пн. ш. 67.31080000002778263° сх. д. / 37.20470000002777766; 67.31080000002778263Витік • координати 38°18′40″ пн. ш. 68°00′41″ сх. д. / 38.3112550000277778° пн. ш. 68.01163300002778556° сх. д. / 38.3112550000277778; 68.01...

 

Policy on permits required to enter Myanmar Politics of Myanmar Constitution 2008 Constitution Constitutional Tribunal Chairman: Than Kyaw National Defence and Security Council Government President (list) Myint Swe (acting) State Administration Council Chairman: Min Aung Hlaing Vice Chairman: Soe Win Vice-President First: Myint Swe Second: Henry Van Thio Prime Minister (list) Min Aung Hlaing Deputy Prime Minister Soe Win Mya Tun Oo Tin Aung San Soe Htut Win Shein Cabinet Provisional Governmen...

Japanese television series Ultraman 80Title cardGenre Tokusatsu Kaiju Superhero Science fiction Action Adventure Kyodai Hero Created byTsuburaya ProductionsDeveloped by Shosuke Ai (eps 1-33) Toshiro Ishido (eps 34-50) Directed byNoriaki YuasaStarring Hatsunori Hasegawa Jin Nakayama Masaaki Daimon Daisuke Musō Shūhei Nitta Eri Ishida Masashi Furuta Tatsuya Okamoto Sayoko Hagiwara Ikuko Wada Mayumi Asano Saburō Bōya ComposerTōru FuyukiCountry of originJapanNo. of episodes50ProductionRunnin...

 

Tournament Director Jack McClelland American poker tournament director and poker player (born 1951) Jack McClellandBorn1951 (age 71–72)World Series of PokerBracelet(s)NoneFinal table(s)4Money finish(es)17World Poker TourMoney finish(es)1Information accurate as of 10 March 2022. Jack McClelland (born 1951) is a poker tournament director and poker player who has had a career in poker operations for more than forty years. He was the WSOP tournament director in the 1980s, and was the t...

 

Airport in Tamaulipas, MexicoNuevo Laredo International AirportAeropuerto Internacional de Nuevo LaredoIATA: NLDICAO: MMNLSummaryAirport typePublicOperatorOlmeca-Maya-MexicaLocationNuevo Laredo, Tamaulipas, MexicoElevation AMSL484 ft / 148 mCoordinates27°26′38″N 099°34′14″W / 27.44389°N 99.57056°W / 27.44389; -99.57056Websitewww.grupoolmecamayamexica.com.mx/laredoMapNLDShow map of TamaulipasNLDShow map of MexicoRunways Direction Length Surfac...

Eurovision Song Contest 2017Country IrelandNational selectionSelection processInternal selectionSelection date(s)Artist: 16 December 2016Song: 10 March 2017Selected entrantBrendan MurraySelected songDying to TrySelected songwriter(s)Jörgen ElofssonJames NewmanFinals performanceSemi-final resultFailed to qualify (13th)Ireland in the Eurovision Song Contest ◄2016 • 2017 • 2018► Ireland participated in the Eurovision Song Contest 2017 with the song Dyi...

 

Breast cancer classification divides breast cancer into categories according to different schemes criteria and serving a different purpose. The major categories are the histopathological type, the grade of the tumor, the stage of the tumor, and the expression of proteins and genes. As knowledge of cancer cell biology develops these classifications are updated. The purpose of classification is to select the best treatment. The effectiveness of a specific treatment is demonstrated for a specifi...

 

The Voice TVTypeBroadcast television networkCountryUK, London, Corporate HeadquartersAvailabilityBulgaria, Denmark, Finland, Sweden, NorwayFounded2004-2012 Scandinavia, Since 2006 BulgariaOwnerProSiebenSat.1 MediaOfficial websitewww.thevoicetv.com The Voice TV is a network of music television channels owned by ProSiebenSat.1 Media (formally SBS Broadcasting Group). Previously broadcast in Finland (2004-2012), Denmark (2004-2012), Norway (2004-2012) and Sweden (2004-2008). In October 2006 the ...

Laure Boulleau Boulleau in 2015Personal informationFull name Laure Pascale Claire BoulleauDate of birth (1986-10-22) 22 October 1986 (age 37)Place of birth Clermont-Ferrand, FranceHeight 1.60 m (5 ft 3 in)[1]Position(s) Left backYouth career1996–2000 FC Moulin-sur-Allier2000–2001 FC Riom2001–2002 Nord Allier Yzeure2002–2003 Entente YssingeauxSenior career*Years Team Apps (Gls)2003–2005 CNFE Clairefontaine 35 (0)2005–2018 Paris Saint-Germain 181 (15)Tota...

 

Main article: Buddhist temples in Japan This is a list of Buddhist temples, monasteries, stupas, and pagodas in Japan for which there are Wikipedia articles, sorted by prefecture. Ehime Kanjizai-ji Fukui Eihei-ji in Eiheiji, Fukui Eihei-ji Fukuoka Nanzoin Shōfuku-ji Jōten-ji Fukushima Enichi-ji Gifu Eihō-ji Shōgen-ji Shōhō-ji Hiroshima Ankoku-ji Buttsū-ji Myōō-in Hyōgo Antai-ji Chōkō-ji Engyō-ji Hōrin-ji Hōun-ji Ichijō-ji Jōdo-ji in Ono Kakurin-ji in Kakogawa Sagami-ji Taisan...

 

1995 Canadian filmButterbox BabiesDVD coverDirected byDon McBreartyWritten byRaymond StoreyBased onButterbox Babies by Bette L. CahillProduced byTrudy GrantKevin SullivanStarringSusan ClarkPeter MacNeillCatherine FitchCinematographyManfred GutheEdited byMairin WilkinsonProductioncompanySullivan EntertainmentRelease date 1995 (1995) CountryCanadaLanguageEnglish Butterbox Babies is a film adapted from the book Butterbox Babies by Bette L. Cahill, which is based on the true story of the Ide...

Tupolev ANT-8 (MDR-2)DescrizioneTipoIdrovolante da ricognizione Equipaggio3 Progettista TsAGIIvan Pogosski CostruttoreIndustrie di Stato URSS Data primo volo30 gennaio 1931 Data entrata in serviziomai Esemplari1 Dimensioni e pesiLunghezza17,03 m Apertura alare23,70 m Altezza5,67 m Superficie alare83,96 m² Peso a vuoto4 560 kg Peso carico6 665 kg Peso max al decollo6 920 kg PropulsioneMotoredue BMW VI, motori 12 cilindri a V raffreddati a liquido Potenza680 CV PrestazioniVeloci...

 

Indian financial services conglomerate IndiabullsTypeConglomerateIndustryFinancial servicesFoundedJanuary 2000HeadquartersIndiabulls House, Udyog Vihar, Gurugram, Haryana, IndiaKey peopleSameer Gehlaut (Chairman & Founder)Abhishek Singh Chauhan (Vice-Chairman & MD)ProductsFinancial servicesReal estatePharmaceuticalConstruction equipment leasingLED lights and facilities sectorDivisionsIndiabulls Housing FinanceDhani ServicesIndiabulls Real EstateWebsitewww.indiabulls.com Old logo of In...

 

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