Minor (teorie grafů)

Minor grafu je rozšířením pojmu podgrafu.

Minor

Minor H grafu G je takový graf, který může vzniknout z nějakého podgrafu G kontrakcemi některých hran.

Indukovaný minor

Indukovaný minor je takový minor, který lze získat kontrakcemi z indukovaného podgrafu.

Topologický minor

Topologický minor je takový, který lze získat z podgrafu pouze topologickými kontrakcemi. To jsou takové, kde alespoň jeden z vrcholů kontrahované hrany má stupeň nejvýše 2.

Minorové operace

Minorovými operacemi se míní odebrání vrcholu, odebrání hrany a kontrakce hrany. To jsou právě ty operace, které jsou zapotřebí k přeměnění grafu na jakýkoli jeho minor. Indukovaný minor se dá získat bez použití operace odebrání hrany.

Alternativní definice

Graf H je minorem grafu G tehdy, když existuje zobrazení f: V(H) → P(V(G)) takové, že:

  1. Pro každé v je f(v) neprázdné a souvislé.
  2. Pro různé u, v jsou f(u), f(v) disjunktní.
  3. Mezi u, v smí být hrana pouze pokud je hrana mezi nějakým vrcholem f(u) a nějakým vrcholem f(v). V případě indukovaného minoru mezi takovými u a v hrana být musí.

Ekvivalence s původní definicí se nahlédne snadno: Po zahození vrcholů mimo f(V(H)) se každá souvislá f(u) dá zkontrahovat do jediného vrcholu. Tak vznikne indukovaný minor, ze kterého se případným odstraněním některých hran získá minor H. Pro opačný směr stačí f(v) nazvat ty vrcholy, které se zkontrahovaly do vrcholu v a ověřit vlastnosti f(v).

Relace „býti minorem“

Relace „býti minorem“ je reflexivní (každý graf je sám sobě triviálním minorem), tranzitivní (každý minor minoru H grafu G je i minorem grafu G) a až na isomorfismus antisymetrická (každá minorová operace sníží počet vrcholů nebo hran). Jedná se tedy o částečné uspořádání. Neil Robertson a Paul Seymour dokázali, že tato relace definuje na třídě všech grafů dobré uspořádání.

Třídy grafů uzavřené na minory

Zakázané minory pro grafy stromové šířky nejvýše 3

Třída grafů F je uzavřená na minory, pokud každý minor nějakého grafu z F je také v F. Důsledkem toho, že minorová relace určuje dobré uspořádání, je to, že se každá taková třída dá charakterizovat konečným počtem zakázaných minorů. Takovéto třídy jsou například:

  • grafy stromové šířky nejvýše k
    • k=1 — lesy — zakázaný minor K3
    • k=2 — sériově paralelní grafy — zakázaný minor K4
    • k=3 — zakázané minory C5◻K2, K5, W8, K2,2,2
  • grafy nakreslitelné bez křížení hran na nějakou plochu
    • rovinné grafy — zakázané minory K5 a K3,3 (minorová Kuratowského věta)
  • všechny grafy — mají prázdnou množinu zakázaných minorů

Externí odkazy

  • Logo Wikimedia Commons Obrázky, zvuky či videa k tématu Minor na Wikimedia Commons

Read other articles:

Daudy Bahari

Biografi ini tidak memiliki sumber tepercaya sehingga isinya tidak dapat dipastikan. Bantu memperbaiki artikel ini dengan menambahkan sumber tepercaya. Materi kontroversial atau trivial yang sumbernya tidak memadai atau tidak bisa dipercaya harus segera dihapus.Cari sumber: Daudy Bahari – berita · surat kabar · buku · cendekiawan · JSTOR (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Daudy Bahari (kanan) Daudy Bahari (lahir 18 Nove...

 

Music of Xenosaga

Music of the video game series Xenosaga The Xenosaga (ゼノサーガ) series is a series of science fiction role-playing video games developed by Monolith Soft and published by Namco Bandai on the PlayStation 2. The series began with the 2002 release of Episode I: Der Wille zur Macht, which was followed in 2004 by Episode II: Jenseits von Gut und Böse and in 2006 by Episode III: Also sprach Zarathustra. The music of Xenosaga includes the soundtracks to all three chapters, as well as the mus...

 

Ahmad Fuad Rahmany

Ahmad Fuad Rahmany Direktur Jenderal PajakMasa jabatan21 Januari 2011 – 1 Desember 2014 PendahuluMochammad TjiptardjoPenggantiSigit Priadi Pramudito Informasi pribadiLahir11 November 1954 (umur 69) SingapuraKebangsaanIndonesiaAlma materUniversitas IndonesiaSunting kotak info • L • B Ahmad Fuad Rahmany atau yang biasa dikenal hanya dengan nama Fuad Rahmany (lahir 11 November 1954) adalah Direktur Jenderal Pajak Kementerian Keuangan Indonesia ke-14 yang menjabat da...

Chiwetel Ejiofor

Chiwetel EjioforCBEEjiofor at the 2016 San Diego Comic-Con International promoting Doctor StrangeLahirChiwetel Umeadi Ejiofor10 Juli 1977 (umur 46)Forest Gate, London, England, United KingdomTempat tinggalLos Angeles, California, U.S.KebangsaanNiegerian, EnglishPendidikanDulwich Prep London Dulwich CollegePekerjaanAktorTahun aktif1995-sekarang Chiwetel Umeadi Ejiofor, OBE (IPA: [/tʃuwɛtəl ɛdʒəfɔː/]; lahir 10 Juli 1977) adalah aktor Britania Raya. Pada tahun 2006, ia me...

 

Koridor 8 Trans Semarang

Terminal Cangkiran - Simpang Lima via GunungpatiArmada Bus Trans Semarang Koridor 8Informasi umumDaerah operasiKota SemarangOperator saat iniPT Mekar Flamboyan Sendang Mulyo JayaPeta rute lbsTrans Semarang Koridor 8 Legenda Terminal Cangkiran, Mijen Pertigaan Cangkiran Tambangan Kelurahan Bubakan Bubakan Kampung Sebumi Polaman Sikretek Losari Sekolo Pandean Siwogo Terminal Gunungpati Kampung Ngrembel SMP 22 Kampung Getas Kandri FK Unwahas Pongangan Desa Wisata Kandri Kuwasen Goa Kreo Kelurah...

 

Conspiracy theories about the death of Diana, Princess of Wales

Innocent Victims, one of two memorials previously displayed in Harrods There are many conspiracy theories surrounding the death of Diana, Princess of Wales, on 31 August 1997.[1] Official investigations in both Britain and France found that Diana died in a manner consistent with media reports following the fatal car crash in Paris. In 1999, a French investigation concluded that Diana died as the result of a crash.[2] The French investigator, Judge Hervé Stephan, concluded th...

Renewable energy in South Africa

Primary sources of renewable energy in South Africa are solar, wind, hydroelectric, and biomass. Pictured here are wind turbines in Darling, Cape Province. Renewable energy in South Africa is energy generated in South Africa from renewable resources, those that naturally replenish themselves—such as sunlight, wind, tides, waves, rain, biomass, and geothermal heat.[1] Renewable energy focuses on four core areas: electricity generation, air and water heating/cooling, transportation, ...

 

Goyband

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (September 2009) (Learn how and when to remove this message) 2008 American filmGoybandFilm posterDirected byChristopher GrimmWritten byChrista McNameeDan Bar HavaChristopher GrimmProduced byChristopher J. ScottDavid SchiavoneRed Sky PicturesStarringAdam PascalAmy DavidsonNatasha LyonneTovah FeldshuhCris JuddEdite...

 

Roustam Raza

Bodyguard of Napoleon Roustan redirects here. For people with surname Roustan, see Roustan (surname). Roustam RazaLe Mamelouk Roustam Raza by Jacques-Nicolas Paillot de Montabert, 1806BornRostam1783Tiflis, Kingdom of Kartli-Kakheti (present-day Tbilisi, Georgia) DiedDecember 7, 1845 (aged 61–62)Dourdan, FranceCitizenshipFranceSpouseAlexandrine DouvilleChildrenAchille Roustam Raza (Armenian: Ռուստամ Ռուզա, Georgian: რუსტამ რაზა; 1783 – 7 Decembe...

List of number-one EPs in the United Kingdom

Donovan never had a number-one single or number-one album in his native UK;[1] however, his Universal Soldier EP spent eight weeks at the top of the EP chart. In the 1950s and 1960s a third vinyl format was introduced alongside long-playing (LP) albums, and singles. The extended play (EP) used the same formats as singles but contained more tracks.[2] Singles were the popular record format at the time – predominantly 10-inch 78 rpm and 7-inch 45 rpm formats[3] &#...

 

Blackpool North (UK Parliament constituency)

Parliamentary constituency in the United Kingdom, 1945–1997 53°51′47″N 2°54′50″W / 53.863°N 2.914°W / 53.863; -2.914 Blackpool NorthFormer Borough constituencyfor the House of CommonsBlackpool North in Lancashire, showing boundaries used from 1974-1983CountyLancashire1945–1997SeatsOneCreated fromBlackpoolReplaced byBlackpool North and Fleetwood Blackpool North was a borough constituency in Lancashire which returned one Member of Parliament to the House ...

 

شرف فتح الباب (مسلسل)

شرف فتح الباب النوع دراما تأليف محمد جلال عبد القوي إخراج رشا شربتجي بطولة يحيى الفخرانىهالة فاخرأحمد خليلمحمد لطفي البلد مصر عدد الحلقات 30 بث لأول مرة في 1 رمضان 1429 هـ - 1 سبتمبر 2008 تعديل مصدري - تعديل   شرف فتح الباب مسلسل مصري إنتاج عام 2008 بطولة للفنان (يحيى الفخراني القص...

Sekolah Islam HASMI Islamic Boarding School Bogor

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada April 2016. artikel ini perlu dirapikan agar memenuhi standar Wikipedia. Tidak ada alasan yang diberikan. Silakan kembangkan artikel ini semampu Anda. Merapikan artikel dapat dilakukan dengan wikifikasi atau membagi artikel ke paragraf-paragraf. Jika sudah dirapikan...

 

Mid-Eastern Athletic Conference

American collegiate athletic conference Mid-Eastern Athletic ConferenceAssociationNCAAFounded1970CommissionerSonja O. Stills (since 2022)Sports fielded 14 men's: 6 women's: 8 DivisionDivision ISubdivisionFCSNo. of teams8HeadquartersNorfolk, VirginiaRegionSouth Atlantic, Middle AtlanticOfficial websitemeacsports.comLocations Part of a series onAfrican Americans History Periods Timeline Atlantic slave trade Abolitionism in the United States Slavery in the colonial history of the US Revolutionar...

 

James Dwight Dana

American scientist (1813–1895) James Dwight DanaDana in 1865Born(1813-02-12)February 12, 1813Utica, New YorkDiedApril 14, 1895(1895-04-14) (aged 82)New Haven, ConnecticutNationalityAmericanScientific careerFieldsgeology, mineralogy, zoologyAuthor abbrev. (zoology)Dana Signature James Dwight Dana FRS FRSE (February 12, 1813 – April 14, 1895) was an American geologist, mineralogist, volcanologist, and zoologist. He made pioneering studies of mountain-building, volcanic activity, a...

Song Without End

1960 film by Charles Vidor, George Cukor Song Without EndVHS coverDirected byCharles VidorWritten byOscar MillardProduced byWilliam GoetzStarringDirk BogardeCapucineGeneviève PageCinematographyJames Wong HoweEdited byWilliam LyonMusic byMorris StoloffHarry SukmanFranz LisztDistributed byColumbia PicturesRelease date August 11, 1960 (1960-08-11) Running time141 min.CountryUnited StatesLanguageEnglishBudget$3.5 million[1]Box office$1,500,000 (US and Canada rentals)[2...

 

Glenolden, Pennsylvania

Borough in Pennsylvania, United States Borough in Pennsylvania, United StatesGlenolden, PennsylvaniaBoroughGazebo in Glenolden ParkLocation in Delaware County and the U.S. state of Pennsylvania.GlenoldenLocation of Glenolden in PennsylvaniaShow map of PennsylvaniaGlenoldenGlenolden (the United States)Show map of the United StatesCoordinates: 39°53′56″N 75°17′33″W / 39.89889°N 75.29250°W / 39.89889; -75.29250CountryUnited StatesStatePennsylvaniaCountyDelawar...

 

مربع بوليبيوس

الحروف اليونانية في مربع بوليبيوس مربع بوليبيوس هو مربع وصفه المؤرخ اليوناني بوليبيوس سنة 150 قبل الميلاد.[1] استعمل إساسا من قبل العدميين القابعين في سجون القياصرة الروس. يعتبر المربع إحدى طرق التشفير، أين يتم استبدال كل حرف بإحداثياته من الأرقام التي توافق طولا وعرضا �...

Société de géographie autrichienne

Société de géographie autrichienneHistoireFondation 1856CadreType Société scientifique, éditeur académique, société de géographieSiège ViennePays  AutricheOrganisationMembres 2 065 (1902), 1 300Publication Mitteilungen der Oesterreichische Geographische GesellschaftSite web www.geoaustria.ac.atmodifier - modifier le code - modifier Wikidata La Société de géographie autrichienne (Österreichische Geographische Gesellschaft, OGG) est une société savante autrichien...

 

Cornsweet illusion

Optical illusion In an example of the Cornsweet illusion, the whole left half of this rectangle seems to be lighter than the right. In fact they have the same brightness, apart from the gradients in the center. The same image as above, but the edge in the middle is hidden: the left and right part of the image appear as the same color. The Cornsweet illusion, also known as the Craik–O'Brien–Cornsweet illusion or the Craik–Cornsweet illusion, is an optical illusion that was described in d...