Subgraf indus

În teoria grafurilor, un subgraf indus al unui graf este un alt graf, format dintr-o submulțime a nodurilor grafului și din toate muchiile (din graful originar) care conectează perechile de noduri din acea submulțime.

Definiție

Formal, fie orice graf și fie orice submulțime de noduri ale lui G. Atunci subgraful indus este graful a cărui mulțime de noduri este și a cărui mulțime de muchii constă din toate muchiile din care au ambele puncte finale în . [1] Adică pentru oricare două noduri , și sunt adiacente în dacă și numai dacă sunt adiacente în . Aceeași definiție este valabilă pentru grafuri neorientate, grafuri orientate și chiar multigrafuri.

Subgraful indus poate fi numit și subgraful indus în de , sau (dacă contextul face ca alegerea lui să fie neambiguă) subgraful indus al lui .

Exemple

Printre tipurile importante de subgrafuri induse se numără următoarele.

Problema șarpelui în cutie⁠(d) se referă la cele mai lungi drumuri induse⁠(d) în grafurile hipercub⁠(d).

Calcul

Problema izomorfismului subgrafurilor induse⁠(d) este o formă a problemei izomorfismului subgrafurilor⁠(d) în care scopul este de a testa dacă un graf poate fi găsit ca subgraf indus al altuia. Deoarece include problema clicii drept caz special, este o problemă NP-completă.[4]

Note

  1. ^ Diestel, Reinhard (), Graph Theory, Graduate texts in mathematics, 173, Springer-Verlag, pp. 3–4, ISBN 9783540261834 .
  2. ^ Howorka, Edward (), „A characterization of distance-hereditary graphs”, The Quarterly Journal of Mathematics, Second Series, 28 (112), pp. 417–420, doi:10.1093/qmath/28.4.417, MR 0485544 .
  3. ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (), „The strong perfect graph theorem”, Annals of Mathematics⁠(d), 164 (1), pp. 51–229, arXiv:math/0212070 Accesibil gratuit, doi:10.4007/annals.2006.164.51, MR 2233847 .
  4. ^ Johnson, David S. (), „The NP-completeness column: an ongoing guide”, Journal of Algorithms, 6 (3), pp. 434–451, doi:10.1016/0196-6774(85)90012-4, MR 0800733 .

Read other articles:

Kepatihan, Banyuwangi, Banyuwangi

KepatihanKelurahanKantor Kelurahan KepatihanPeta lokasi Kelurahan KepatihanNegara IndonesiaProvinsiJawa TimurKabupatenBanyuwangiKecamatanBanyuwangiKodepos68411Kode Kemendagri35.10.16.1008 Kode BPS3510180008 Luas... km2Jumlah penduduk... jiwaKepadatan... jiwa/km2 Untuk tempat lain yang bernama sama, lihat Kepatihan. Fort Utrecht di Kepatihan pada tahun 1920-an. Sebuah karya mural di bangunan kosong dekat perempatan Sritanjung (Masjid Agung Baiturrahman Banyuwangi) pada tahun 2014 Gerbang ...

 

Katedral Maronit Tirus

Katedral TirusGereja Katedral Katolik Maronit Bunda Lautan di TirusKatedral TirusLokasiTirusNegara LebanonDenominasiGereja Katolik Roma (sui iuris: Gereja Maronit)SejarahDedikasiBunda LautanArsitekturStatusKatedralStatus fungsionalAktifAdministrasiKeuskupanEparki Agung Tirus Katedral Maronit Bunda Lautan, Tirus adalah sebuah gereja katedral Katolik yang terletak di kota Tirus, negara Lebanon. Katedral ini menjadi pusat kedudukan dan takhta bagi Eparki Agung Tirus.[1] Galeri Inter...

 

Keuskupan Agung Melbourne

Keuskupan Agung MelbourneArchidioecesis MelburnensisKatolik Katedral St Patrick, MelbourneLokasiNegaraAustraliaWilayahMelbourneProvinsi gerejawiMelbourneKoordinat37°48′32″S 144°58′46″E / 37.80889°S 144.97944°E / -37.80889; 144.97944StatistikLuas27.194 km2 (10.500 sq mi)Populasi- Total- Katolik(per 2013)Kenaikan 4.095.921Kenaikan 1,111,981 ( 27.1%)Paroki 216InformasiDenominasiKatolik RomaRitusRitus LatinPendirian31 Maret 18...

Azali Assoumani

Artikel ini perlu dikembangkan agar dapat memenuhi kriteria sebagai entri Wikipedia.Bantulah untuk mengembangkan artikel ini. Jika tidak dikembangkan, artikel ini akan dihapus. 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: Azali Assoumani – berita...

 

2007–08 Coppa Italia

Football tournament season 2007–08 Coppa ItaliaRoma players are given the trophy by Italian president Giorgio Napolitano after the finalTournament detailsCountry ItalyDates14 Aug 2007 – 24 May 2008Teams42Final positionsChampionsRoma (9th title)Runner-upInternazionaleTournament statisticsMatches played55Goals scored160 (2.91 per match)Top goal scorer(s)Mario BalotelliJulio CruzVincenzo Iaquinta Giampaolo Pazzini (4 goals each)← 2006–072008–09 →...

 

2023 in UFC

UFC MMA events in 2023 2023 in UFCInformationFirst dateJanuary 14, 2023 (2023-01-14)Last dateDecember 16, 2023 (2023-12-16)EventsTotal events43UFC14TUF Finale events1FightsTotal fights520Title fights21Chronology 2022 in UFC 2023 in UFC 2024 in UFC The year 2023 was the 30th year in the history of the Ultimate Fighting Championship (UFC), a mixed martial arts promotion based in the United States. UFC in 2023 UFC merged with WWE to form TKO Group In April 2023, End...

新罕布什尔州

坐标：43°11′38″N 71°34′21″W / 43.1938516°N 71.5723953°W / 43.1938516; -71.5723953 此條目需要补充更多来源。 (2017年5月21日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一下条目的标题（来源搜索：新罕布什尔州 — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源...

 

Новотитаровское сельское поселение

Сельское поселение России (МО 2-го уровня)Новотитаровское сельское поселение Флаг[d] Герб 45°14′09″ с. ш. 38°58′16″ в. д.HGЯO Страна  Россия Субъект РФ Краснодарский край Район Динской Включает 4 населённых пункта Адм. центр Новотитаровская Глава сельского пос�...

 

2016年美國總統選舉

2016年美國總統選舉 ← 2012 2016年11月8日 2020 → 538個選舉人團席位獲勝需270票民意調查投票率55.7%[1][2] ▲ 0.8 %   获提名人 唐納·川普 希拉莉·克林頓 政党 共和黨 民主党 家鄉州 紐約州 紐約州 竞选搭档 迈克·彭斯 蒂姆·凱恩 选举人票 304[3][4][註 1] 227[5] 胜出州/省 30 + 緬-2 20 + DC 民選得票 62,984,828[6] 65,853,514[6]...

Athletics Papua New Guinea

Athletics Papua New GuineaSportAthleticsFounded1961 (1961)AffiliationWorld AthleticsAffiliation date1962 (1962)Regional affiliationOAAHeadquartersKokopo, East New BritainPresidentTony GreenVice president(s)Sophia MaraiSecretaryGeorge MoramoroReplacedPapua New Guinea Athletic UnionOfficial websitewww.foxsportspulse.com/assoc_page.cgi?c=2-1148-0-0-0 Athletics Papua New Guinea (Athletics PNG) is the governing body for the sport of athletics in Papua New Guinea. Current president is Ton...

 

2009 Oxfordshire County Council election

2009 UK local government election 2009 Oxfordshire County Council election ← 2005 4 June 2009 2013 → All 74 seats to Oxfordshire County Council38 seats needed for a majority   Majority party Minority party Third party   Party Conservative Liberal Democrats Labour Last election 43 16 8 Seats won 51 10 9 Seat change 8 5 1 Percentage 42.81% 23.87% 15.09%   Fourth party Fifth party   Party Green Independent Last election 5 2 Seats ...

 

Tori Kelly

American singer-songwriter (born 1992) Tori KellyKelly in 2023BornVictoria Loren Kelly (1992-12-14) December 14, 1992 (age 31)[1]Wildomar, California, U.S.OccupationsSingersongwriteractressYears active2003–presentSpouse André Murillo ​(m. 2018)​Musical careerOriginCanyon Lake, California, U.S.GenresR&Bpopsoulgospel[2]Instrument(s)VocalsguitarLabelsEpicBeautiful MindCapitolSchoolboyGeffen Musical artistWebsitetorikellymusic.comSigna...

Carom billiards

Billiards games played on cloth-covered pocketless tables Not to be confused with the board game carrom. Carom billiardsA carom billiard table and billiard ballsHighest governing bodyUnion Mondiale de Billard (UMB)First played18th century FranceCharacteristicsContactNoTeam membersSingle opponents, doubles or teamsMixed-sexYes, sometimes in separate leagues/divisionsTypeIndoor, table, cue sportEquipmentBilliard ball, billiard table, cue stickVenueBilliard hall or home billiard roomPresenc...

 

Bindae-tteok

Korean fried mung bean pancake Bindae-tteokBindae-tteok being fried in Gwangjang MarketAlternative namesMung bean pancake, nokdu-buchimgae, nokdu-jeon, nokdu-jeonbyeong, nokdu-jijimTypeBuchimgaePlace of originKoreaAssociated cuisineKorean cuisineMain ingredientsMung beansFood energy(per 1 serving)35 kcal (147 kJ)[1]Other informationKorean nameHangul빈대떡Revised Romanizationbindae-tteokMcCune–Reischauerpindae-ttŏkIPA[pin.dɛ̝.t͈ʌk̚]   Media: Bindae...

 

Constitution of Syria

Fundamental law of the Second Syrian Republic (1950-63) and modern Syria Part of a series onBa'athism OrganisationsArab Ba'ath1940–1947Arab Ba'ath Movement1940–1947Ba'ath Party1947–1966Baath Party (pro-Iraqi)1968–2003Baath Party (pro-Syrian)1966–present People Zaki al-Arsuzi Michel Aflaq Salah al-Din al-Bitar Abdullah Rimawi Wahib al-Ghanim Fuad al-Rikabi Salah Jadid Hafez al-Assad Ahmed Hassan al-Bakr Saddam Hussein Bashar al-Assad Izzat Ibrahim al-Douri Literat...

Ecology of the San Francisco Estuary

San Francisco Estuary The San Francisco Estuary together with the Sacramento–San Joaquin River Delta represents a highly altered ecosystem. The region has been heavily re-engineered to accommodate the needs of water delivery, shipping, agriculture, and most recently, suburban development. These needs have wrought direct changes in the movement of water and the nature of the landscape, and indirect changes from the introduction of non-native species. New species have altered the architectur...

 

Tara Sands

American voice actress Tara SandsSands in 2016Other namesTara JayneOccupationsVoice actresstelevision hostYears active1998–presentWebsitewww.tarasands.com Tara Sands is an American voice actress and co-host of Cartoon Network's Fridays from 2005 to 2007.[1] Sands has voiced in anime dubs and cartoons, including Bulbasaur in the Pokémon anime series, Spyler in I Spy, Kari Kamiya in Digimon Adventure tri., Anna Kyoyama in Shaman King, Mokuba Kaiba in Yu-Gi-Oh! Duel Monsters...

 

Миллер, Алексей Борисович

В Википедии есть статьи о других людях с такой фамилией, см. Миллер; Миллер, Алексей. Алексей Борисович Миллер Имя при рождении Алексей Борисович Миллер Дата рождения 31 января 1962(1962-01-31)[1] (62 года) Место рождения Ленинград, РСФСР, СССР Страна  СССР Россия Род д�...

Сергієвський (парк-пам'ятка садово-паркового мистецтва)

Сергіївський парк46°01′08″ пн. ш. 30°21′20″ сх. д. / 46.018890000027774079° пн. ш. 30.35583000002777965° сх. д. / 46.018890000027774079; 30.35583000002777965Координати: 46°01′08″ пн. ш. 30°21′20″ сх. д. / 46.018890000027774079° пн. ш. 30.35583000002777965° сх. д. / 46.018890000027774079; 30.355...

 

فاتنة (قبعة)

فاتنةكاثرين دوقة كامبريدج مرتدية فاتنة حمراء خلال زيارتها لكندا عام 2011معلوماتالنوع عمرةتعديل - تعديل مصدري - تعديل ويكي بيانات الفاتنة هي عمرة رسمية، وهي نمط من القبعات. منذ التسعينيات، يشير المصطلح إلى نوع من أغطية الرأس الرسمية التي ترتدى كبديل للقبعة؛ عادة ما تكون تصمي...