Grafikus matroid

A matematika által vizsgált egyik struktúratípus a matroid. A grafikus matroid vagy körmatroid (esetleg gráfmatroid), olyan matroidot jelent, melynek

  • alaphalmaza/univerzuma egy adott irányítatlan gráf éleinek halmaza;
  • maga a struktúra pedig ennek olyan részhalmazaiból áll, melyek nem tartalmaznak kört, azaz körmentes részgráfot, erdőt alkotnak (kör az olyan véges, de nem üres élsorozat, melyben minden él mindkét végpontja egy másik élnek is végpontja). A körmentes részgráfokat nevezzük tehát függetlennek.

A matroidaxiómák teljesülése gráfmatroidokra

A legkönnyebb azt belátni, hogy egy gráf erdőt alkotó részgráfjainak halmaza teljesíti az ún. „izokardinalitási” axiómarendszert.

  1. Az üres halmaz erdő, mivel nem tartalmaz kört (ahogy általában semmit sem). Ez tehát független.
  2. Erdő minden részhalmaza is erdő, ha lenne egy ilyenben kör, akkor azt persze az eredeti, bővebb erdő is tartalmazná. Tehát független részhalmaz részhalmaza is független.
  3. A harmadik axióma szerint tetszőleges két maximális erdőnek azonos élszámúnak kell lennie a gráfban. Ez egy gráfelméleti tétel alapján tényleg igaz, nevezetesen a maximális független erdők élszáma a pontok és a gráf komponenseinek (a maximális – azaz egymástól diszjunkt – összefüggő részgráfok) számának különbsége.

Ám a bővíthetőségi axiómarendszer teljesülése egyszerűbben is igazolható.


Egyebek

  • Belátható, hogy a grafikus matroidok mindegyike gyakorlatilag tetszőleges T test felett lineárisan reprezentálható (azaz mátrixmatroid).
  • A gráf persze egyértelműen meghatározza a hozzá tartozó körmatroidot. Fordítva azonban ez nem igaz. Ugyanazon körmatroidhoz különféle gráfok tartozhatnak. Persze egy gráf sokféleképp „rajzolható meg”, de az az érdekes, hogy még ha az izomorfiát is tekintetbe vesszük, akkor sincs egyértelműség. Két nem izomorf gráf körmatroidja lehet izomorf. A legegyszerűbb példa: bármely két k-élű fa körmatroidja izomorf, mert a fák tetszőleges részgráfja erdő (körmentes), és így független. Azonban maga a két fa nem feltétlenül izomorf (aki tanult szerves kémiát, az tudja, hogy ez mennyire igaz). De meglehetősen könnyű másféle, kis élszámú ellenpélda-párokat is konstruálni.

Körök

Egy gráfban körnek nevezünk egy olyan véges élsorozatot, melyre, ha , akkor ha , azaz ha út, és még is teljesül (azaz zárt út).


Külső hivatkozások

Read other articles:

Untuk kegunaan lainnya, lihat Daya (disambiguasi). DayaSimbol umumPSatuan SIwattDalam satuan pokok SIkg⋅m2⋅s−3Turunan daribesaran lainnyaP = E/tP = F·vP = V·I Bagian dari seri artikel mengenaiMekanika klasik F → = m a → {\displaystyle {\vec {F}}=m{\vec {a}}} Hukum kedua Newton Sejarah Garis waktu Cabang Benda langit Dinamika Kinematika Kinetika Kontinuum Statika Statistika Terapan Dasar Asas D'Alembert Daya mekanik Energi kinetik potensial Gaya Impuls Inersia / Mome...

 

Poem by George Herbert The poem in a Baroque architectural frame from the 1670 edition of George Herbert's The Temple The Altar is a shaped poem by the Welsh-born poet and Anglican priest George Herbert, first published in his posthumous collection The Temple (1633). The poem is founded on a Baroque metaphor with a long history of prior use of coalescing verbal and visual image. The popularity of the collection in which it appeared is attested by eleven editions during the 17th century and a ...

 

Mountain-climbing cog railway in New Hampshire, United States For the defunct railway in Los Angeles, see Los Angeles and Mount Washington Railway. Mount Washington Cog RailwayTrack with rackOverviewLocaleCoos County, New Hampshire, U.S.HistoryOpened1868TechnicalLine length3 miles (4.8 km)[1]Rack systemMarsh rack systemTrack gauge4 ft 8 in (1,422 mm) Route map Legend Mount Washington summit Appalachian Trail Skyline siding(removed) Waumbek station and pa...

ISO 14000 عائلة من المعايير ذات الصلة للإدارة البيئية الموجودة لمساعدة المنظمات (أ) تقليل كيفية تأثير العمليات (الأعمال الصناعية، إلخ.) سلبا على البيئة (أي تسبب تغيرات سلبية في الهواء أو الماء أو الأرض)؛ (ب) الامتثال للقوانين المعمول بها واللوائح الأخرى الموجهة بيئيا؛ و (ج) تحسن �...

 

2046Poster film 2046Indeks kartuSutradaraWong Kar-waiProtagonisTony Leung Chiu Wai Zhang Ziyi Faye Wong Takuya KimuraProduksi seni pertunjukanWong Kar-waiNaskahWong Kar-wai MusikShigeru Umebayashi dan Peer Raben FotografiChristopher Doyle, Kwan Pun Leung dan Lai Yiu-fai Penyuntingan filmWilliam Chang DistributorJet Tone Films LtdPenampilan perdana2004 Durasi129 menitBahasa asli (film atau acara televisi)Mandarin Kanton Jepang Warnaberwarna Format2.35:1 BudgetUS$ 12.000.000 (perkiraan)Deskrip...

 

Artikel ini bukan mengenai PSBS Batu Sangkar atau PSBS Bangkinang. PSBS BiakNama lengkapPersatuan Sepakbola Biak dan SekitarnyaJulukanBadai PasifikNama singkatPSBSBerdiri12 Desember 1964; 59 tahun lalu (1964-12-12)StadionStadion Cendrawasih(Kapasitas: 15,000)PemilikPT Biak SportindoKetuaHerry Ario NaapManajerYan MandenasPelatihRegi Aditya YonathanLigaLiga 12023–24Liga 2 Juara (promosi) Kostum kandang Kostum tandang Kostum ketiga Musim ini Persatuan Sepakbola Biak dan Sekitarnya (umumny...

2019 Nigerian film The MillionsMovie posterDirected byToka McBarorWritten byTunde ApalowoScreenplay byTunde ApalowoStory byTunde ApalowoProduced byChika LannStarringRamsey NouahBlossom ChukwujekwuToyin AbrahamEdited byTunde ApalowoMusic byAva MomohProductioncompanyChika Lann ProductionsDistributed byFilmOne DistributionRelease date 30 August 2019 (2019-08-30) Running time94 minutesCountryNigeriaLanguageEnglishBudget₦62 millionBox office₦19.3 million The Millions is a 2019 N...

 

Here We Go!Album Studio karya ArashiDirilis12 Juli 2002 (2002-07-12) (Jepang)16 Agustus 2002 (2002-08-16) (Taiwan)GenrePop, Hip hop, R&BDurasi61:15LabelJ StormJACA-5002 (Edisi Terbatas)JACA-5003 (Edisi Normal)Kronologi Arashi Arashi Single Collection 1999-2001(2002)String Module Error: Match not found2002 Here We Go!(2002) How's It Going?(2003)String Module Error: Match not found2003 Singel dalam album Here We Go! A Day in Our LifeDirilis: 06 Februari 2002 (2002-02-06)...

 

Arrigo Petacco nel 1973 Arrigo Petacco (Castelnuovo Magra, 7 agosto 1929 – Portovenere, 3 aprile 2018) è stato un giornalista, storico e sceneggiatore italiano. È stato inviato speciale, caporedattore e direttore de La Nazione di Firenze e del mensile Storia Illustrata, nonché autore di programmi televisivi di argomento storico. Indice 1 Biografia 2 Opere 2.1 Prefazioni e curatele 3 Programmi televisivi 4 Onorificenze 5 Note 6 Altri progetti 7 Collegamenti esterni Biografia Una scena del...

German footballer (1929–2003) 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: Helmut Rahn – news · newspapers · books · scholar · JSTOR (March 2021) (Learn how and when to remove this message) Helmut Rahn Rahn in 1962Personal informationDate of birth (1929-08-16)16 August 1929Place of birth Essen, GermanyD...

 

Joan of FranceJoan with her mother, Blanche of Navarre, and Saint Louis.BornMay 1351Died16 September 1371(1371-09-16) (aged 20)Béziers, FranceBurialBasilica of St Denis, Saint-Denis, FranceHouseValoisFatherPhilip VI of FranceMotherBlanche of Navarre Joan of France (May 1351 – 16 September 1371), also known as Blanche, was the only child of Philip VI of France and his second wife Blanche of Navarre. Joan was born nine months after her father's death. Life Joan's maternal grandparents w...

 

Мечеть в Сураттхани Ислам в Таиланде — со второй половины XX века приобретает всё большее распространения. Это вторая по количеству верующих религия в государстве. Её исповедуют населяющие Таиланд малайцы, пакистанцы, тамилы и пенджабцы, а также беженцы-чамы из соседн...

خالد بن منصور بن لؤي معلومات شخصية الوفاة 1351هـ - 1933مصبيا - جازان الخدمة العسكرية الولاء إمارة نجد الفرع إخوان من طاع الله المعارك والحروب توحيد المملكة العربية السعودية ضم الحجاز الثورة العربية الكبرى معركة الطائف معركة مكة (1924) معركة جدة (1925) إدخال بلاد غامد وزهران للحكم ا�...

 

American multinational mass media corporation (2013–2019) This article is about the corporation that was active from 2013 until 2019. For other uses, see 21st Century Fox (disambiguation). For the corporation that replaced 21st Century Fox after the sale, see Fox Corporation. Not to be confused with 21st Century Film Corporation. Twenty-First Century Fox, Inc.Logo used from 2013 to 2019Headquarters of 21st Century Fox on 1211 Avenue of the AmericasTrade name21st Century FoxCompany typePubli...

 

Demographics of Equatorial GuineaPopulation pyramid of the Equatorial Guinea in 2020Population1,679,172 (2022 est.)Growth rate3.5% (2022 est.)Birth rate29.95 births/1,000 population (2022 est.)Death rate8.95 deaths/1,000 population (2022 est.)Life expectancy63.7 years • male61.44 years • female66.03 yearsFertility rate4.26 children born/woman (2022 est.)Infant mortality rate78.33 deaths/1,000 live birthsNet migration rate13.96 migrant(s)/1,000 population (2022 es...

British Indian civil servant (1851–1926) SirKrishna Govinda GuptaKCSIস্যার কৃষ্ণগোবিন্দ গুপ্তBorn(1851-02-28)28 February 1851Bhatpara, Narsingdi,[1] British IndiaDied20 March 1926(1926-03-20) (aged 75)Calcutta, British IndiaOccupationCivil servantSignature Sir Krishna Govinda Gupta KCSI (Bengali: স্যার কৃষ্ণগোবিন্দ গুপ্ত; 28 February 1851 – 20 March 1926) was a British Indian civ...

 

لاعب الشهر في الدوري الإسبانيمعلومات عامةالرياضة كرة القدم البلد  إسبانيا أول جائزة 2013 موقع الويب laligapotm.easports.com (الإسبانية) تعديل - تعديل مصدري - تعديل ويكي بيانات يحمل ليونيل ميسي الرقم القياسي لعدد جوائز لاعب الشهر في الدوري الإسباني مناصفةً مع أنطوان غريزمان بـ8 جوائز....

 

Cet article est une ébauche concernant une localité italienne et la Vénétie. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Falcade Noms Nom allemand Pfalden Administration Pays Italie Région Vénétie  Province Belluno  Code postal 32020 Code ISTAT 025019 Préfixe tel. 0437 Démographie Gentilé fALCADINI Population 1 830 hab. (31-10-2020[1]) Densité 35 hab./km2 Géographie Coord...

Emilio Lavagnino, anni '50 Emilio Lavagnino (Roma, 22 agosto 1898 – Ginevra, 12 aprile 1963) è stato uno storico dell'arte e critico d'arte italiano. La sua figura può essere accostata a quella di Rodolfo Siviero, per l'impegno da entrambi profuso nella difesa del patrimonio artistico italiano dalle spoliazioni e dai trafugamenti nazisti durante la seconda guerra mondiale Indice 1 Biografia 1.1 Seconda guerra mondiale 1.2 Opere scelte 1.3 Letteratura e documentaristica 2 Note 3 Altri prog...

 

This article is about the region. For the continent, see Antarctica. For other uses, see Antarctic (disambiguation). Polar region around Earth's South Pole A map of the Antarctic region, including the Antarctic Convergence and the 60th parallel south The Antarctic Plate The Antarctic (/ænˈtɑːrtɪk/ or /ænˈtɑːrktɪk/, American English also /æntˈɑːrtɪk/ or /æntˈɑːrktɪk/; commonly /æˈnɑːrtɪk/)[Note 1] is a polar region around Earth's South Pole, opposite the Arctic...