Sűrű gráf

A matematika, azon belül a gráfelmélet területén egy sűrű gráf alatt olyan gráfot értünk, melyben az élek száma közel áll az élek maximális lehetséges számához. Ennek az ellentéte, a ritka gráf a viszonylag kevés éllel rendelkező gráf. A sűrű és ritka gráfok közötti különbségtétel önkényes, a szövegkörnyezettől függhet.

Irányítatlan egyszerű gráfokon egy gráf sűrűsége a következővel egyezik meg:

Irányított egyszerű gráfok sűrűsége pedig így határozható meg:

ahol E a gráf éleinek, V a csúcsainak a száma. Irányítatlan gráfban az élek maximális száma ½ |V| (|V|−1), tehát a maximális sűrűség 1 (a teljes gráfok esetében), a minimális pedig 0 (Coleman & Moré 1983).

Felső sűrűség

A felső sűrűség a gráfsűrűség fogalmának kiterjesztése véges gráfokról végtelen gráfokra. Intuitív megközelítésben egy végtelen gráfnak lehetnek a felső sűrűségénél kisebb sűrűségű, tetszőlegesen nagy véges részgráfjai, de nem lehetnek a felső sűrűségnél nagyobb sűrűségű, tetszőlegesen nagy véges részgráfjai. Formálisan, egy G gráf felső sűrűsége azon α értékek infimuma, melyekre G α sűrűségű véges részgráfjai korlátos számú csúccsal rendelkezhetnek. Az Erdős–Stone-tétel segítségével megmutatható, hogy a felső sűrűség értéke vagy 1, vagy a szuperpartikuláris arányok valamelyike: 0, 1/2, 2/3, 3/4, 4/5, ... n/(n + 1), ... (lásd pl. Diestel, p. 189).

Ritka és éles gráfok

(Lee & Streinu 2008) és (Streinu & Theran 2009) definíciója szerint egy (k,l)-ritka gráf (sparse graph) minden nem üres részgráfjának n csúcsa között legfeljebb kn − l él húzódik, a (k,l)-éles gráf (tight graph)[1] pedig (k,l)-ritka és pontosan kn − l éllel rendelkezik. Így a fák az (1,1)-éles gráfokkal egyeznek meg, az erdők az (1,1)-ritka gráfok, a k arboricitású gráfok pedig a (k,k)-ritka gráfok. A pszeudoerdők (az összefüggő komponensenként legfeljebb 1 körrel rendelkező irányítatlan gráfok) az (1,0)-ritka gráfokkal egyeznek meg, a merevségelmélet Laman-gráfjai pedig a (2,3)-éles gráfokkal.

Más, a ritkaságukkal nem jellemezhető gráfcsaládokról is tehetők hasonló kijelentések. Például az n csúcsú síkgráfok legfeljebb 3n − 6 éllel rendelkeznek, és bármely síkgráf részgráfjai is síkgráf – ebből a két kijelentésből következik, hogy a síkgráfok (3,6)-ritka gráfok. Nem igaz viszont, hogy bármely (3,6)-ritka gráf síkgráf lenne. Hasonlóan kijelenthető, hogy a külsíkgráfok (2,3)-ritkák és a páros síkgráfok (2,4)-ritkák.

Streinu és Theran igazolta, hogy a (k,l)-ritkaságra való tesztelés polinom időben elvégezhető, ha k és l olyan egész számok, melyekre 0 ≤ l < 2k.

Ha egy gráfcsalád esetén létezik olyan k és l, melyekre a családbéli gráfok (k,l)-ritkák, akkor a gráfok degeneráltsága vagy arboricitása korlátos. Precízebben kimondva, (Nash-Williams 1964) eredményéből következik, hogy a legfeljebb a arboricitású gráfok éppen az (a,a)-ritka gráfok; a legfeljebb d degeneráltságú gráfok pedig éppen a ((d + 1)/2,1)-ritka gráfok.

Ritka és sűrű gráfosztályok

(Nešetřil & Ossona de Mendez 2010) arra jutott, hogy a ritkaság/sűrűség dichotómia miatt szükséges egyes gráfok helyett végtelen gráfosztályokat tekintetbe venni. Úgy definiálták a valahol sűrű (somewhere dense) gráfosztályt, mint azokat a gráfosztályokat, melyekben létezik t küszöbérték, melyre minden teljes gráf megjelenik az osztály egy gráfjának t-felosztásaként. Ha ilyen küszöbérték nem létezik, a gráfosztály sehol sem sűrű (nowhere dense). A sehol sem sűrű és valahol sűrű gráfosztályok dichotómiáját (Nešetřil & Ossona de Mendez 2012) elemzik.

A korlátos degeneráltságú gráfok és a sehol sem sűrű gráfok mind beletartoznak a biklikkmentes gráfok osztályába, melyek a teljes páros gráfot részgráfként nem tartalmazó gráfcsaládok(Telle & Villanger 2012).

Kapcsolódó szócikkek

Fordítás

  • Ez a szócikk részben vagy egészben a Dense graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

  1. az „éles” szó itt a matematikai zsargonban használt éles, tovább már nem javítható eredményre utal

Read other articles:

Sheikh Saeed Al Maktoum House dengan menara angin di Al Shindagha. Saeed Al Maktoum House merupakan sebuah bangunan bersejarah dan bekas kediaman Saeed bin Maktoum Al Maktoum, bekas pemimipin Dubai di Uni Emirat Arab. Bangunan ini terletak di tepi Dubai Creek di wilayah pemukiman Al Shindagha. Didirikan sekitar 1894 sebagai kediaman keluarga Al Maktoum. Bangunan ini sekarang menjadi museum yang berisi artefak dan gambar kota tua Dubai.[1] Catatan kaki ^ HOUSE OF SHEIKH SAEED AL-MAKTOO...

 

1-Butuna H − C ≡ C − C | H H | − C | H H | − H {\displaystyle {\ce {H-C#C}}{-}{\ce {\overset {\displaystyle {H} \atop |}{\underset {| \atop \displaystyle {H}}{C}}}}{-}{\ce {\overset {\displaystyle {H} \atop |}{\underset {| \atop \displaystyle {H}}{C}}}}{\ce {-H}}} Nama Nama IUPAC (preferensi) But-1-una Nama lain EtilasetilenaEtiletuna, UN 2452 Penanda Nomor CAS 107-00-6 Y Model 3D (JSmol) Gambar interaktif 3DMet {{{3DMet}}} ChEBI CHEBI:48087 Y Che...

 

Lembah Fergana. Lembah Fergana atau Ferghana ialah daerah di Asia Tengah yang tersebar melintasi Uzbekistan, Tajikistan dan Kirgizstan. Makam Ali di Shakhimardan, di sisi Lembah Ferghana. Kini masih merupakan enklaf kecil di Uzbekistan yang diapit Kirgiztan. Kesatuan geografi dan politik yang sederhana dari kebanyakan sejarahnya, hanya pada 1920-an dan 1930-an saat Lembah Ferghana dibagi antara 3 negara yang berbeda (RSS Uzbekistan, RSS Kirgistan dan RSS Tajikistan). Di bawah Khan dari Kokand...

Slipping G.W.R. Mail coaches at Pylle Hill, Bedminster, Bristol, UK A slip coach, slip carriage or slip portion in Britain and Ireland, also known as a flying switch in North America, is one or more carriages designed to be uncoupled from the rear of a moving train.[a] The detached portion continued under its own momentum following the main train until slowed by its own guard using the brakes, bringing the slip to a stop, usually at the next station. The coach or coaches were thus sa...

 

Portuguese politician You can help expand this article with text translated from the corresponding article in Portuguese. (September 2018) Click [show] for important translation instructions. View a machine-translated version of the Portuguese article. 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-transla...

 

يوشيرو موري森 喜朗 (باليابانية: 森喜朗)‏  رئيس وزراء اليابان في المنصب5 أبريل 2000 – 26 أبريل 2001 العاهل أكيهيتو ميكيو أوكي جونيتشيرو كويزومي وزير النقل في المنصب8 أغسطس 1995 – 11 يناير 1996 رئيس الوزراء تومي-إتشي موراياما كوكين نوساكا إيتشي ناأوكا وزارة التجارة الخارجية والصناعة �...

Chronologie de la France ◄◄ 1682 1683 1684 1685 1686 1687 1688 1689 1690 ►► Chronologies La statue originale de Louis XIV, place des Victoires (1686)Données clés 1683 1684 1685  1686  1687 1688 1689Décennies :1650 1660 1670  1680  1690 1700 1710Siècles :XVe XVIe  XVIIe  XVIIIe XIXeMillénaires :-Ier Ier  IIe  IIIe Chronologies thématiques Art Architecture, Arts plastiques (Dessin, Gravure, Peinture et Sculpture), Littératur...

 

Wilayah Brigantes Brigantes adalah suku Seltik yang pada masa pra-Romawi menguasai wilayah Inggris utara dan sebagian Midlands. Kerajaan mereka dikenal sebagai Brigantia, dan berpusat di tempat yang kini merupakan Yorkshire. Brigantes adalah satu-satunya suku Seltik yang dapat ditemui baik di Inggris maupun Irlandia. Di Inggris, wilayah yang dihuni Brigantes berbatasan dengan empat suku Seltik: Carvetii di barat laut, Parisii di timur dan Corieltauvi dan Cornovii di selatan. Pranala luar Brig...

 

Season of television series Love Live! Nijigasaki High School Idol ClubPromotional artworkNo. of episodes26ReleaseOriginal networkTokyo MXOriginal releaseOctober 3, 2020 (2020-10-03) –June 25, 2022 (2022-06-25)Season chronology← PreviousLove Live! Sunshine!! Next →Love Live! Superstar!! List of episodes Love Live! Nijigasaki High School Idol Club is an anime television series produced by Bandai Namco Filmworks (under the Sunrise brand) as the third installment i...

1975 picture book Why Mosquitoes Buzz in People's Ears AuthorVerna AardemaIllustratorLeo and Diane DillonCover artistDillonsCountryUnited StatesGenreChildren's picture bookPublisherDial BooksPublication date1975ISBN0-8037-6089-2OCLC1094805Dewey Decimal[398.2] ELC ClassPZ8.1.A213 Wh Why Mosquitoes Buzz in People's Ears: A West African Tale is a 1975 children's picture book by Verna Aardema and illustrated by Leo and Diane Dillon. Published in hardcover by Dial Books for Young Readers...

 

Statement about a future event For other uses, see Prediction (disambiguation). predict redirects here. For other uses, see predict (disambiguation). The Old Farmer's Almanac is famous in the US for its (not necessarily accurate) long-range weather predictions. A prediction (Latin præ-, before, and dictum, something said[1]) or forecast is a statement about a future event or about future data. Predictions are often, but not always, based upon experience or knowledge of forecasters. T...

 

Class of compounds Alpha-1 blockers (also called alpha-adrenergic blocking agents or alpha-1 antagonists) constitute a variety of drugs that block the effect of catecholamines on alpha-1-adrenergic receptors. They are mainly used to treat benign prostatic hyperplasia (BPH), hypertension and post-traumatic stress disorder.[1] Alpha-1 adrenergic receptors are present in vascular smooth muscle, the central nervous system, and other tissues. When alpha blockers bind to these receptors in ...

اليَسَر «بفتح الياء والسين» هو الشخص الذي يستعمل يده اليمنى في نشاطاته اليومية كالأكل والشرب والكتابة والطبخ وغيرها. اليَسَر في اللغة اليَسَر (بفتح الياء والسين) عكس الأعسر، ويقال: رجلٌ أعْسَرُ بَيِّن العَسَرِ، للذي يعمل بيساره. وأمَّا الذي يعمل بكلتا يديه فهو أعْسَرُ يَ�...

 

For the American rock band, see Brownsville Station (band). Miami-Dade Transit metro station ● BrownsvilleMetrorail metro stationBrownsville Transit Village in 2012General informationLocation5200 NW 27th AvenueMiami, FloridaCoordinates25°49′19″N 80°14′26″W / 25.82194°N 80.24056°W / 25.82194; -80.24056Owned byMiami-Dade CountyPlatforms2 side platformsTracks2Connections Metrobus: 27, 54ConstructionParkingPark and ride (423 spaces)AccessibleYesOther informat...

 

HR 8799 e كوكب خارج المجموعة الشمسية قائمة الكواكب الخارجية النجم الأم النجم HR 8799 تابع إلى HR 8799[1]  الكوكبة الفرس الأعظم المطلع المستقيم 23سا 07د 28.7150ث[2] الميل +21° 08′ 03.302″[2] القدر الظاهري (mV) 5.964[2] البعد 129 ± 4[3][ملاحظة 1] سنة ضوئية...

Suku RejangTun Jang • Tun HêjangJumlah populasiTidak diketahui secara pasti. ca 350.000 (2010)Daerah dengan populasi signifikan Provinsi Bengkulu340.000 (perkiraan)Sumatera Selatan dan provinsi lainnya di Indonesia10.000 (perkiraan)Bahasa Bahasa ibu: RejangMelayu Bengkulu Bahasa lain yang dituturkan: IndonesiaMelayu Tengah AgamaIslam (mayoritas)Kelompok etnik terkait Suku-suku tetangga penutur bahasa Melayik di wilayah Sumatra Bagian Selatan: BesemahLembakLintangMelayu BengkuluP...

 

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (سبتمبر 2023) NGC 6425   الكوكبة العقرب  رمز الفهرس NGC 6425 (الفهرس العام الجديد)IRAS 17437-3128 (IRAS)C 1743-315 (فهرس كالدويل)IRAS 17437-3131 ...

 

Chemical compound CiglitazoneClinical dataATC codenoneIdentifiers IUPAC name 5-{4-[(1-methylcyclohexyl)methoxy]benzyl}-1,3-thiazolidine-2,4-dione CAS Number74772-77-3 YPubChem CID2750IUPHAR/BPS2711DrugBankDB09201 YChemSpider2648 NUNIIU8QXS1WU8GKEGGD03493 YChEMBLChEMBL7002 NCompTox Dashboard (EPA)DTXSID0040757 ECHA InfoCard100.220.474 Chemical and physical dataFormulaC18H23NO3SMolar mass333.45 g·mol−13D model (JSmol)Interactive image SMILES O=C1NC(=O)SC1Cc3ccc(...

English snooker player (born 1975) Ronnie O'SullivanOBEO'Sullivan at the 2015 German MastersBorn (1975-12-05) 5 December 1975 (age 48)Wordsley, West Midlands, EnglandSport country EnglandNicknameThe Rocket[1]Professional1992–presentHighest ranking1 (May 2002 – May 2003, May 2004 – May 2006, May 2008 – May 2010, March – August 2019, April 2022 – May 2024)Current ranking 5 (as of 16 July 2024)Maximum breaks15Century breaks1,265 (as of 30 July 2024)Tournament winsRa...

 

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article contient une ou plusieurs listes (mars 2024). Ces listes gagneraient à être rédigées sous la forme de paragraphes synthétiques, plus agréables à la lecture, les listes pouvant être aussi introduites par une partie rédigée et sourcée, de façon à bien resituer les différents items.D'autre part, Wikipédia n'a pas pour rôle de constituer une base de données et privilégie un contenu encyc...