היפרגרף

היפרגרף (אנגלית: Hypergraph) הוא הכללה של גרף, שבה כל קשת היא תת-קבוצה לא ריקה של קודקודים. בעוד שבגרף פשוט קשת בין קודקוד וקודקוד מסומנת על ידי הזוג , בהיפרגרף כל קשת היא n-יה (או קבוצה, שכן הסדר חסר חשיבות) של הקודקודים אותם היא מחברת, למשל .

באופן פורמלי, היפרגרף בלתי מכוון מוגדר בדומה לגרף בלתי מכוון, כאשר כל קשת היא קבוצה של צומת אחת או יותר מ-, ומתקיים כי: , כלומר: הקבוצה היא איבר של קבוצת החזקה של הקבוצה .

היפרגרף מכוון מוגדר בדומה לגרף מכוון, כאשר כל קשת מורכבת משתי קבוצות כל אחת בעלת צומת אחד או יותר מ-, קבוצה של צמתים מהם הקשת יוצאת וקבוצה של צמתים אליהם הקשת נכנסת.

היפרגרף נקרא -היפרגרף אם כל קשת מכילה צמתים. בפרט, גרף הוא -היפרגרף.

סדרת הדרגות

הדרגה של צומת בהיפרגרף היא מספר הקשתות בהיפרגרף המכילות את .

סדרת הדרגות של היפרגרף עם צמתים וסדר של הצמתים היא הסדרה . סדרה נקראת -גרפית אם היא סדרת הדרגות של איזשהו -היפרגרף. בעיית ההחלטה האם סדרה נתונה היא -גרפית פתירה בזמן פולינומי עבור ([1] Erdős and Gallai, 1960) אך NP-complete לכל ([2] 2018 ,.Deza et al).

קישורים חיצוניים

הערות שוליים

  1. ^ P. Erdős, T. Gallai, Graphs with prescribed degrees of vertices, Mat. Lopak 11, 1960, עמ' 264-274
  2. ^ Antoine Deza, Asaf Levin, Syed M. Meesum, Shmuel Onn, Optimization over Degree Sequences, SIAM Journal on Discrete Mathematics 32, 2018-01, עמ' 2067–2079 doi: 10.1137/17M1134482


ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.

Read other articles:

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 Oktober 2022. Eksekusi penggergajian tiga orang, dari cetakan abad ke-15[1] Hukuman mati dengan gergaji atau menggergaji adalah jenis hukuman mati yang dilakukan dengan menggergaji atau memotong orang yang hidup menjadi dua, baik secara sagital (biasanya mid...

 

Genie Music CorporationNama asli주식회사 지니뮤직JenisPublik perseroan terbatasKode emitenKRX: 043610IndustriKonten (musik)PendahuluBlue Cord Technology Co., Ltd.(sebagai sebuah divis)Didirikan7 February 1991Kantorpusat106-17 Samseong-dong, Gangnam-gu, Seoul, Korea SelatanWilayah operasiSeluruh duniaTokohkunciKim Hoon-bae (CEO)[1]ProdukAlbum musik, layanan daringJasaProduksi, distribusiPemilikKT Corporation (42.49%)LG Uplus (15%)SM-YG-JYP Konsorsium (7.12%)[2][3 ...

 

Sporting event delegationTurkey at the1960 Winter OlympicsIOC codeTURNOCTurkish National Olympic CommitteeWebsiteolimpiyat.org.tr (in English and Turkish)in Squaw ValleyCompetitors2 (men) in 1 sportMedals Gold 0 Silver 0 Bronze 0 Total 0 Winter Olympics appearances (overview)193619481952195619601964196819721976198019841988199219941998200220062010201420182022 Turkey competed at the 1960 Winter Olympics in Squaw Valley, United States. Turkish athletes competed in the Men's Alpine Downhill,...

Démographie de l’Arménie Pyramide des âges de l'Arménie en 2020 Dynamique Population 3 038 217 hab.(2018)[1] Évolution de la population −0,25 % (2018)[2],[3] Indice de fécondité 1,64 enfant par ♀[4](2018)[5] Taux de natalité 12,6 ‰ (2018)[6],[7] Taux de mortalité 9,5 ‰ (2018)[8],[9] Taux de mortalité infantile 12,3 ‰ (2018)[10] Âges Espérance de vie à la naissance 75,1 ans (2018)[11]Hommes : 7...

 

Community college in New York SUNY ErieFormer namesNew York State Institute of Applied Arts and Sciences at BuffaloErie County Technical InstituteErie Community CollegeTypePublic community collegeEstablished1946; 78 years ago (1946)Parent institutionState University of New YorkPresidentAdiam TsegaiAcademic staff519 (Buffalo campus),[1]607 (North campus),[2]400 (South campus)[3]Undergraduates8,364 (2022)[4]LocationWilliamsville, New York, Unite...

 

Società Sportiva Edera RavennaStagione 1946-1947Sport calcio Squadra Edera Ravenna Allenatore Euro Riparbelli Presidente Mario Gritti Serie C13° Maggiori presenzeCampionato: Baroncini (26) Miglior marcatoreCampionato: Valentino Valli (5) 1945-1946 1947-1948 Si invita a seguire il modello di voce Questa pagina raccoglie le informazioni riguardanti la Società Sportiva Edera Ravenna nelle competizioni ufficiali della stagione 1946-1947. Stagione Nella stagione 1946-47 il Ravenna ha dispu...

Bioregion in Western Australia YalgooWestern AustraliaZuytdorp Cliffs and Edel LandThe interim Australian bioregions,with Yalgoo in redArea50,875.77 km2 (19,643.2 sq mi) Localities around Yalgoo: Shark Bay Carnarvon Murchison Indian Ocean Yalgoo Murchison Geraldton Sandplains Avon Wheatbelt Coolgardie Yalgoo is an interim Australian bioregion located in Western Australia.[1] It has an area of 5,087,577 hectares (12,571,680 acres).[2] The bioregion, together with...

 

British TV series or programme Paddington GreenCreated byLion TelevisionCountry of originUnited KingdomNo. of series6No. of episodes53ProductionRunning time30 minutesOriginal releaseNetworkBBCRelease28 December 1998 (1998-12-28) –24 July 2001 (2001-07-24) Paddington Green is a British television series, which explores the lives of a number of residents of Paddington, London.[1] It was created by Lion Television and was first shown on the BBC in late 1998/early 1999. ...

 

Town in Selangor, Malaysia For other uses, see Banting (disambiguation). Aerial view of Banting in 2023 Banting in Kuala Langat District Banting is a town and the seat of Kuala Langat District, Selangor, Malaysia.[1] Banting has a population of 93,497. The postal code for Banting is 42700 and is administered by the Zone of 15 and 19 of the Kuala Langat Municipal Council. It is situated on the banks of Langat River (Sungai Langat in Malay). It is a Rest Town or Bandar Persinggahan of F...

Bendera Azerbaijan Nama Azərbaycan bayrağı(Bendera Azerbaijan), Üçrəngli bayraq(Bendera Triwarna) Pemakaian Bendera dan bendera kapal nasional Perbandingan 1:2 Dipakai 9 November 1918 (diadopsi kembali 5 Februari 1991) Rancangan Triwarna mendatar berwarna biru, merah, dan hijau; serta terdapat bulan sabit dan bintang berujung delapan di tengahnya. Perancang Ali bey Huseynzade Bendera Azerbaijan ini dipakai oleh pemerintahan sejak tanggal 5 Februari 1991. Bendera ini terdiri dari tiga g...

 

Palazzo Strozzi a Firenze è coronato da un notevole cornicione Il cornicione è un elemento architettonico che svolge la funzione di terminazione superiore di un edificio. Indice 1 Storia e descrizione 2 Gastronomia 3 Note 4 Voci correlate 5 Altri progetti Storia e descrizione Palazzo Curtius (Liegi), cornicione Presenta normalmente andamento orizzontale e sporge in modo più o meno accentuato rispetto alla parete esterna dell'edificio, decorato con modanature e talvolta mensole. Può assume...

 

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています(詳細)。 数字の大字(だいじ)は、漢数字の一種。通常用いる単純な字形の漢数字(小字)の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券(「壱」が大字) 弐千円日本銀行券(「弐」が大字) 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

密西西比州 哥伦布城市綽號:Possum Town哥伦布位于密西西比州的位置坐标:33°30′06″N 88°24′54″W / 33.501666666667°N 88.415°W / 33.501666666667; -88.415国家 美國州密西西比州县朗兹县始建于1821年政府 • 市长罗伯特·史密斯 (民主党)面积 • 总计22.3 平方英里(57.8 平方公里) • 陸地21.4 平方英里(55.5 平方公里) • ...

 

كرة القدم في ألعاب البحر الأبيض المتوسط 2005تفاصيل المسابقةالبلد المضيف إسبانياالتواريخ23 يونيو - 3 يونيوالفرق9 (من 2 اتحاد كونفدرالي)الأماكن4 (في 4 مدن مضيفة)المراكز النهائيةالبطل إسبانيا (1 لقب)الوصيف تركياالمركز الثالث ليبياالمركز الرابع المغربإحصائيات �...

 

الجماهيرية العظمى هي الاسم الرسمي لنظام الحكم في ليبيا في عهد معمر القذافي. و ترد في الاسم الرسمي للدولة الليبية في ذلك العهد الجماهيرية العربية الليبية الشعبية الاشتراكية العظمى. وهي من أفكار العقيد معمر القذافي التي طرحها في الكتاب الأخضر، أول ورود لهذا الاسم كان في الث�...

Basket-ball aux Jeux olympiques d'été de 1956 Généralités Sport Basket-ball Éditions 4e Lieu(x) Melbourne Nations 15[1] Participants 169[1] Épreuves 1 Palmarès Tenant du titre États-Unis Vainqueur États-Unis Deuxième URSS Troisième Uruguay Navigation Helsinki 1952 Rome 1960 modifier Résultats du tournoi de basket-ball aux Jeux olympiques d'été de 1956 à Melbourne. Médaillés Or Argent Bronze États-UnisK.C. JonesBurdie HaldorsonCarl CainGilbert FordRichard BoushkaJim Wal...

 

Bahasa Itbayat Itbayaten Ibatan Dituturkan diFilipina dan TaiwanWilayahItbayat dan LanyuEtnisIvatanYamiPenutur(3.500 per 1996)[1] Rumpun bahasaAustronesia Melayu-PolinesiaBatanikYami–ItbayatItbayat Kode bahasaISO 639-3taoGlottologitba1237[2]Lokasi penuturanItbayat dan bahasa Batanik lainnya.Peta bahasa lain Portal BahasaL • B • PW        PemberitahuanTemplat ini mendeteksi bahwa artikel bahasa ini masih belum dinilai...

 

Pyroxene mineral DiopsideDiopside – Bellecombe, Châtillon, Aosta Valley, ItalyGeneralCategoryInosilicate mineralFormula(repeating unit)MgCaSi2O6IMA symbolDi[1]Strunz classification9.DA.15Crystal systemMonoclinicCrystal classPrismatic (2/m) (same H-M symbol)Space groupC2/cUnit cella = 9.746 Å, b = 8.899 Å c = 5.251 Å; β = 105.79°; Z = 4IdentificationColorCommonly light to dark green; may be blue, brown, colorless, white to snow white, grey, pale violetC...

РСДРП — РСДРП(б) — РКП(б) —ВКП(б) — КПССИстория партии Октябрьская революция (1917) Военный коммунизм (1918—1921) Новая экономическая политика (1921—1928) Ленинский призыв (1924) Внутрипартийная борьба (1926—1933) Сталинизм (1933—1953) Хрущёвская оттепель (1953—1964) Период застоя (1964—1985) Перес...

 

HemşinՀամշինիHemşin in Russia nel 1905 Nomi alternativiHemshinli, Khemshil, Hamsheni Luogo d'origineHemşin (Turchia) Popolazione500,000 - 700,000 LinguaArmeno, turco ReligioneIslam sunnita hanafita, Cristianesimo ortodosso armeno Gruppi correlatiarmeni Distribuzione  Turchia500,000 - 700,000 Russia Armenia Georgia Manuale Gli Hemşin[1][2] (conosciuti anche come Hamsheni, Hemshinli o Khemshil; Համշինի in armeno; Hemşinli in turco...