Teorema de Menger

Em teoria dos grafos e áreas relacionadas da matemática, o teorema de Menger é um resultado básico sobre conectividade em grafos finitos não direcionados. Foi provada a K-aresta-conectividade e K-vértice-conectividade por Karl Menger em 1927. A versão para aresta-conectividade do teorema de Menger foi generalizada mais tarde pelo Teorema do Fluxo Máximo–Corte Mínimo.

A versão do teorema de Menger para aresta-conectividade funciona da seguinte forma:

G é um grafo finito não direcionado e x e y são dois vértices distintos. Então o teorema afirma que o tamanho mínimo de arestas que precisam ser removidas para desconectar x e y é igual ao número máximo de caminhos aresta-independentes emparelhados de x para y.
Estendendo para subgrafos: um subgrafo maximal desconectado por não menos que k-arestas de corte é idêntico aos subgrafo maximal com um número mínimo de k caminhos aresta-independente entre qualquer par de nós x, y no subgrafo.

A versão do teorema de Menger para vértice-conectividade funciona da seguinte forma:

G é um grafo finito não direcionado e x e y são dois vértices não adjacentes. Então o teorema afirma que o número mínimo de vértices que precisam ser removidos para desconectar x e y é igual ao número máximo de caminhos vértice-independentes emparelhados de x para y.
Estendendo para subgrafos: um subgrafo maximal desconectado por não menos que k-vértices de corte é identico aos subgrafo maximal com um número mínimo de k caminhos vértice-independente entre qualquer par de nós x, y no subgrafo.

Grafos infinitos

O teorema de Menger é valido para grafos infinitos, e nesse contexto se aplica ao corte mínimo entre quaisquer dois elementos que ou são vértices ou extremidades do grafo (Halin 1974). O resultado a seguir é um resultado de Ron Aharoni e Eli Berger e foi originalmente uma conjectura proposta por Paul Erdős, e antes de ser provada ficou conhecida como A conjectura Erdős–Menger. É equivalente ao teorema de Menger quando o grafo é finito.

A e B são conjunto de vértices em um (possivelmente infinito) digrafo G. Então existe uma família P de A-B-caminhos disjuntos e um conjunto separador de exatamente um vértice para cada caminho em P.

Ver também

Referências

Ligações externas

Read other articles:

Via et veritas et vita

Motto tersebut dalam lambang kota Arad, Rumania. Via et veritas et vita (Latin Klasik: [ˈwi.a ˈweːritaːs ˈwiːta], Latin Gerejawi: [ˈvi.a ˈveritas ˈvita]) adalah sebuah frase Latin yang artinya jalan dan kebenaran dan hidup. Kata-kta tersebut diambil dari versi Vulgata dari Yohanes 14:6, dan diucapkan oleh Yesus Kristus untuk merujuk kepada dirinya sendiri. Kata tersebut, dan terkadang varian asindetiknya via veritas vita, dipakai sebagai motto berbagai lembaga pendidikan da...

 

Friendship, Oklahoma

Town in Oklahoma, United StatesFriendship, OklahomaTownFriendship state historical markerFriendshipShow map of OklahomaFriendshipShow map of the United StatesCoordinates: 34°41′52″N 99°13′43″W / 34.69778°N 99.22861°W / 34.69778; -99.22861CountryUnited StatesStateOklahomaCountyJacksonArea[1] • Total0.15 sq mi (0.39 km2) • Land0.15 sq mi (0.39 km2) • Water0.00 sq mi (0.00...

 

Fiammamonza 1993-1994

Voce principale: Fiamma Monza 1970. Fiammamonza PrecaStagione 1993-1994Sport calcio SquadraFiamma Monza 1970 Allenatore Fabrizio Levati All. in seconda Angelo Margutti Presidente Natalina Ceraso Levati Serie A8º posto. Coppa ItaliaOttavi di finale. StadioStadio Gino Alfonso Sada 1992-1993 1994-1995 Si invita a seguire il modello di voce Questa voce raccoglie le informazioni riguardanti la Fiammamonza Preca[1] nelle competizioni ufficiali della stagione 1993-1994. Indice 1 Rosa 2 Squ...

Lazarevac

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

 

Francesco Di Tacchio

Francesco Di Tacchio Nazionalità  Italia Altezza 185 cm Peso 81 kg Calcio Ruolo Centrocampista Squadra  Ascoli CarrieraGiovanili 2005-2008 Ascoli2009-2010 FiorentinaSquadre di club1 2008-2009 Ascoli12 (0)2009-2010 Fiorentina0 (0)2010-2011→  Frosinone20 (1)2011-2012→  Juve Stabia12 (0)2012-2013→  Perugia12 (1)2013-2015 Entella60 (2)[1]2015-2017 Pisa48 (1)[2]2017-2018 Avellino39 (1)2018-2022 Salernitana117 ...

 

Пугачёва, Алла Борисовна

Запрос «Пугачёва» перенаправляется сюда; см. также другие значения. Алла Пугачёва На фестивале «Славянский базар в Витебске», 2016 год Основная информация Полное имя Алла Борисовна Пугачёва Дата рождения 15 апреля 1949(1949-04-15) (75 лет) Место рождения Москва, СССР[1]...

Metal Up

2015 studio album by Miracle of SoundMetal UpStudio album by Miracle of SoundReleasedMarch 31, 2015Recorded2015GenreHeavy metalRockLength55:17ProducerGavin DunneMiracle of Sound chronology Vistas(2014) Metal Up(2015) Level 6(2015) Metal Up is a heavy metal album by Miracle of Sound. Some of its songs are based on Irish folklore, and the album stayed at the top of the iTunes Metal charts for 2 days following its release in March 2015.[1] Metal Up was described as mix of classi...

 

Friday's Child (Will Young song)

2004 single by Will Young Friday's ChildSingle by Will Youngfrom the album Friday's Child Released5 July 2004 (2004-07-05)Length 9:02 (album version) 4:10 (single version) Label 19 S RCA BMG Songwriter(s) Stephen Lee Dina Taylor Producer(s)Stephen LipsonWill Young singles chronology Your Game (2004) Friday's Child (2004) Switch It On (2005) Friday's Child is a song by British singer Will Young. It was written by Stephen Lee and Dina Taylor and produced by Stephen Lipson for You...

 

Scotiabank

Canadian multinational bank headquartered in Toronto 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: Scotiabank – news · newspapers · books · scholar · JSTOR (March 2018) (Learn how and when to remove this message) Bank of Nova ScotiaScotia Plaza in TorontoTrade nameScotiabankCompany typePublicTraded asTSX:&...

Aspen parkland

Temperate grasslands, savannas, and shrublands ecoregion of Canada and the United States Aspen parklandAspen parkland near Calgary, AlbertaAspen parkland within CanadaEcologyRealmNearcticBiomeTemperate grasslands, savannas, and shrublandsBorders List Alberta-British Columbia foothills forestsCentral British Columbia Mountain forestsMid-Continental Canadian forestsMontana Valley and Foothill grasslandsMuskwa-Slave Lake forestsNorth Central Rockies forestsNorthern Cordillera forestsNorthern mix...

 

Ipsen

IpsenJenisSociété anonymeIndustriFarmasi industriDidirikan1929KantorpusatParisTokohkunciDavid Loew, CEOKaryawan5,700Situs webwww.ipsen.com Ipsen adalah perusahaan farmasi Prancis yang berbasis di Paris, Prancis.[1] Perusahaan ini mengkhususkan diri dalam tiga bidang terapi: onkologi, ilmu saraf, dan penyakit langka. Ini diperdagangkan secara publik di Euronext Paris sebagai bagian dari indeks SBF 120 (2005). Ipsen, didirikan oleh Henri Beaufour pada tahun 1929, memiliki lebih dari 5...

 

آكس أون بروفانس

  آكس أون بروفانس (بالفرنسية: Aix-en-Provence)‏(بالأكستانية: Ais de Provença)‏(بالفرنسية: Aix)‏    آكس أون بروفانس آكس أون بروفانس  خريطة الموقع تقسيم إداري البلد فرنسا[1][2]  [3][4] عاصمة لـ كونتية بروفانس  [لغات أخرى]‏آكس أون بروفانس  [لغات أخرى]‏ك�...

Masao Yoshida (baseball)

Japanese baseball player Masao Yoshida Masao Yoshida (吉田 正男, Yoshida Masao, April 14, 1914 – May 23, 1996) was a Japanese amateur pitcher originally from Ichinomiya, Aichi. He had 23 wins at Spring and Summer Koshien. In the National High School Baseball Championship between 1931 and 1933, he won 14 consecutive games at Koshien Stadium and he became the only pitcher to win three consecutive championships. Three consecutive high school championships Yoshida entered Chukyo Shogyo. He ...

 

The Andrew Marr Show

British TV series or programme The Andrew Marr ShowAlso known asSunday AM (2005–2007)Sunday MorningGenrePoliticsPresented byAndrew MarrCountry of originUnited KingdomOriginal languageEnglishProductionProduction locationsStudio 54D, New Broadcasting House, LondonRunning time60 minutesOriginal releaseNetworkBBC OneRelease11 September 2005 (2005-09-11) –19 December 2021 (2021-12-19)RelatedBreakfast with FrostSunday with Laura Kuenssberg The Andrew Marr Show is a Sunday mornin...

 

Lara Robinson

Australian actress (born 1998) Lara RobinsonBorn (1998-01-01) 1 January 1998 (age 26)Melbourne, Victoria, AustraliaOccupation(s)Actress, SingerYears active2006–present Lara Robinson (born 1 January 1998) is an Australian actress who has appeared in films, television series, and theatre productions. Career Robinson has appeared in a remake of a 1978 Australian thriller Long Weekend starring Claudia Karvan as well as an American science fiction drama, Knowing, starring Nicolas Cage ...

ハービー・ハンコック

ハービー・ハンコックHerbie Hancock ハービー・ハンコック（1999年）基本情報出生名 Herbert Jeffrey Hancock生誕 (1940-04-12) 1940年4月12日（84歳）出身地 アメリカ合衆国 イリノイ州シカゴジャンル ジャズポスト・バップモード・ジャズフュージョンジャズ・ファンク職業 ミュージシャン作曲家担当楽器 キーボード活動期間 1961年 -レーベル ブルーノート・レコードコロムビア・レ�...

 

Gefühlte Temperatur

Unter der gefühlten Temperatur versteht man die wahrgenommene Umgebungstemperatur, die sich aufgrund verschiedener Faktoren von der gemessenen Lufttemperatur unterscheiden kann. Es handelt sich um ein bioklimatisches Maß für das thermische Wohlbefinden und umfasst das Spektrum vom Wärme- bzw. Hitzegefühl über Behaglichkeit bis zum Kältegefühl. Bei Säugetieren und Vögeln mit gleich bleibenden Körpertemperaturen kann gefühlte Kälte je nach Konditionierung von einem Zittern begleite...

 

寧龍客語

此條目需要补充更多来源。 (2013年10月8日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一下条目的标题（来源搜索：寧龍客語 — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。 寧龍片Nèn-liùŋ-phién母语国家和地区 中国区域主条目：客家地區 主要分佈�...

Public land

Land owned by a national, subnational, or local government In all modern states, a portion of land is held by central or local governments. This is called public land, state land, or Crown land (Commonwealth realms). The system of tenure of public land, and the terminology used, varies between countries. The following examples illustrate some of the range. Commonwealth realms In several Commonwealth realms such as Australia, New Zealand and Canada, public lands are referred to as Crown lands....

 

Long métrage

Photo tirée de The Story of the Kelly Gang (1906) Un long métrage (également écrit long-métrage) est un film de cinéma d'une durée significative, dont la définition précise dépend des normes reconnues selon les pays ou organisations. Histoire Définition En France, selon les textes en vigueur du Centre national du cinéma et de l'image animée, la durée d'un long métrage est plus exactement supérieur ou égal à 58 minutes et 29 secondes, c'est-à-dire l'équivalent d'une bobine ...