Tutte matrix

In graph theory, the Tutte matrix A of a graph G = (V, E) is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once.

If the set of vertices is then the Tutte matrix is an n-by-n matrix A with entries

where the xij are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables xij, i < j ): this coincides with the square of the pfaffian of the matrix A and is non-zero (as a polynomial) if and only if a perfect matching exists. (This polynomial is not the Tutte polynomial of G.)

The Tutte matrix is named after W. T. Tutte, and is a generalisation of the Edmonds matrix for a balanced bipartite graph.

References

  • R. Motwani, P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. p. 167.
  • Allen B. Tucker (2004). Computer Science Handbook. CRC Press. p. 12.19. ISBN 1-58488-360-X.
  • W.T. Tutte (April 1947). "The factorization of linear graphs" (PDF). J. London Math. Soc. 22 (2): 107–111. doi:10.1112/jlms/s1-22.2.107. Retrieved 2008-06-15.


Stub icon

This graph theory-related article is a stub. You can help Wikipedia by expanding it.

Stub icon

This article about matrices is a stub. You can help Wikipedia by expanding it.

Read other articles:

Bojong, Pekalongan

BojongKecamatanPeta lokasi Kecamatan BojongNegara IndonesiaProvinsiJawa TengahKabupatenPekalonganPopulasi • Total62,978 jiwa (BPS 2.013) jiwaKode Kemendagri33.26.11 Kode BPS3326110 Luas40.06 km²Desa/kelurahan22 Kediaman residen Pekalongan di Bojong pada tahun 1880-an (litografi oleh Josias Cornelis Rappard) Bojong (Jawa: ꦧꦺꦴꦗꦺꦴꦁ, translit. Bojong) adalah sebuah kecamatan di Kabupaten Pekalongan, Provinsi Jawa Tengah, Indonesia. Kecamatan ini berjarak s...

 

Kedutaan Besar Republik Indonesia di Den Haag

Kedutaan Besar Republik Indonesia di Den HaagAmbassade van de Republiek Indonesië in Den HaagKoordinat52°05′10″N 4°17′19″E / 52.08614°N 4.288721°E / 52.08614; 4.288721Lokasi Den Haag, BelandaAlamatTobias Asserlaan 8, 2517 KCDen Haag, BelandaDuta BesarMayerfasYurisdiksi BelandaSitus webkemlu.go.id/thehague/id Kedutaan Besar Republik Indonesia di Den Haag (KBRI Den Haag) (Belanda: Ambassade van de Republiek Indonesië in Den Haagcode: nl is deprecated )...

 

Soil texture

Property of a soil Soil texture is a classification instrument used both in the field and laboratory to determine soil classes based on their physical texture. Soil texture can be determined using qualitative methods such as texture by feel, and quantitative methods such as the hydrometer method based on Stokes' law. Soil texture has agricultural applications such as determining crop suitability and to predict the response of the soil to environmental and management conditions such as drought...

العلاقات الفلبينية الكندية

العلاقات الفلبينية الكندية الفلبين كندا   الفلبين   كندا تعديل مصدري - تعديل   العلاقات الفلبينية الكندية هي العلاقات الثنائية التي تجمع بين الفلبين وكندا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارنة الفلبي�...

 

Île Jan Mayen

Vous lisez un « article de qualité » labellisé en 2007. Pour les articles homonymes, voir Jan et Mayen (homonymie). Île Jan Mayen Drapeau Carte de localisation de l'île Jan Mayen au sein du comté de Nordland. Administration Statut politique Territoire de la Norvège administré par le comté de Nordland Capitale Olonkinbyen Gouvernement- Roi de Norvège- Gouverneur Monarchie constitutionnelleHarald VÅshild Hauan Démographie Population 18 hab. (2010) Densité 0,05 ...

 

Jules Wijdenbosch

7th President of Suriname Jules Wijdenbosch7th President of SurinameIn office15 September 1996 – 12 August 2000Vice PresidentPretaap RadhakishunPreceded byRonald VenetiaanSucceeded byRonald Venetiaan2nd Vice President of SurinameIn office7 January 1991 – 16 September 1991PresidentJohan KraagPreceded byHenck ArronSucceeded byJules AjodhiaPrime Minister of SurinameIn office7 April 1987 – 26 January 1988PresidentFred Ramdat MisierPreceded byPretaap RadhakishunSuc...

Joara

Archaeological site in North Carolina, United States of America Location of Joara in present-day Burke County, North Carolina Joara was a large Native American settlement, a regional chiefdom of the Mississippian culture, located in what is now Burke County, North Carolina, about 300 miles from the Atlantic coast in the foothills of the Blue Ridge Mountains.[1] Joara is notable as a significant archaeological and historic site, where Mississippian culture-era and European artifacts ha...

 

Janet Woodcock

This biographical article is written like a résumé. Please help improve it by revising it to be neutral and encyclopedic. (January 2022) American physician Janet WoodcockPrincipal Deputy Commissioner of Food and DrugsIncumbentAssumed office February 18, 2022PresidentJoe BidenPreceded byAmy AbernethyCommissioner of Food and DrugsActingIn officeJanuary 20, 2021 – February 17, 2022PresidentJoe BidenPreceded byStephen HahnSucceeded byRobert CaliffDirector of the Center for Drug E...

 

Qesem cave

Archaeological site Qesem caveמערת קסם‎Qesem CaveShown within IsraelLocationCentral District, near the town of Kafr QasimHistoryPeriodsLower Paleolithic Qesem cave is a Lower Paleolithic archaeological site near the town of Kafr Qasim in Israel. Early humans were occupying the site by 400,000 until c. 200,000 years ago. The karstic cave attracted considerable attention in December 2010, when reports suggested Israeli and Spanish archaeologists had found the earliest evidence yet ...

Woodstock – Back to the Garden: 50th Anniversary Experience

2019 live album by various artistsWoodstock – Back to the Garden: 50th Anniversary ExperienceLive album by various artistsReleasedJune 28, 2019RecordedAugust 15–18, 1969VenueWoodstock festivalGenreRockLength12:41:04LabelRhinoProducerAndy ZaxSteve WoolardBrian KehewWoodstock albums chronology Woodstock – Back to the Garden: 50th Anniversary Collection(2019) Woodstock – Back to the Garden: 50th Anniversary Experience(2019) Woodstock – Back to the Garden: The Definitive 50th An...

 

ヨハネス12世 (ローマ教皇)

ヨハネス12世 第130代 ローマ教皇 教皇就任 955年12月16日教皇離任 964年5月14日先代 アガペトゥス2世次代 レオ8世個人情報出生 937年スポレート公国（中部イタリア）スポレート死去 964年5月14日 教皇領、ローマ原国籍 スポレート公国親 父アルベリーコ2世（スポレート公）、母アルダその他のヨハネステンプレートを表示 ヨハネス12世（Ioannes XII、937年 - 964年5月14日）は、ロ...

 

Nome de la Bât

Hiéroglyphe symbole du Nome. Le nome de la Bât (bȝt) est l'un des 42 nomes (division administrative) de l'Égypte antique. C'est l'un des vingt-deux nomes de la Haute-Égypte et il porte le numéro sept. Ville principale Diospolis Parva Les nomes de Haute-Égypte v · mNomes et villes d'Égypte antique Nomes Basse-Égypte 1er : Nome de la Muraille blanche 2e : Nome de la Cuisse 3e : Nome de l'Occident 4e : Nome inférieur de Neith 5e : Nome supérieur de Neith...

Charles Fourier

Charles FourierLahirFrançois Marie Charles Fourier(1772-04-07)7 April 1772Besançon, PrancisMeninggal10 Oktober 1837(1837-10-10) (umur 65)Paris, PrancisEraFilsuf abad ke-19KawasanFilsuf BaratAliranSosialisme utopisFourierismeMinat utamaPeradaban · Kerja · Ekonomi · KeinginanKomunitas intensionalGagasan pentingPhalanstèreAttractive work Dipengaruhi Nicolas-Edme Rétif[1] Memengaruhi Pierre-Joseph Proudhon, Joseph Déjacque, Karl Marx, Pet...

 

Stato sociale in Italia

Voce principale: Stato sociale. Lo stato sociale italiano (o del welfare o del benessere) è l’insieme delle politiche pubbliche che proteggono i cittadini nei confronti di bisogni e rischi quali la nascita, la malattia, la vecchiaia, gli infortuni, la disabilità, la disoccupazione, ovvero l’insieme delle politiche sociali. Manifestazione sindacale, Genova, 1976. Il ruolo dello stato nel sociale in realtà è cambiato nel corso della storia ed il concetto di stato sociale è emerso nel ...

 

Taekwondo pada Pekan Olahraga Nasional XIX – +73 kg putri

Taekwondo padaPekan Olahraga Nasional XIX Poomsae Putra Putri   Perorangan     Perorangan     Beregu Beregu Kyorugi Putra Putri   54 kg     46 kg     58 kg 49 kg 63 kg 53 kg 68 kg 57 kg 74 kg 62 kg 80 kg 67 kg 87 kg 73 kg +87 kg +73 kg Taekwondo lebih dari 73 kg putri pada Pekan Olahraga Nasional XIX dilaksanakan pada tanggal 25 september 2016 di Gymnasium FPOK, Universitas Pendidikan Indonesia, Kota Bandung, Jawa Barat.[1] Jadwa...

Zainal Mus

Zainal Mus adalah seorang politikus Indonesia. Dari 2009 sampai 2014, ia menjabat sebagai Ketua Dewan Perwakilan Rakyat Daerah (DPRD) Kabupaten Kepulauan Sula. Dari 2017 sampai 2022, ia menjabat sebagai Bupati Banggai Kepulauan. Pada 11 Februari 2023, ia mengundurkan diri selaku anggota Partai Golkar Maluku Utara dan kemudian bergabung dengan Partai Gerindra. Dewan Pimpinan Daerah (DPD) Partai Gerindra Maluku Utara mendorongnya untuk maju dalam pemilihan umum Bupati Banggai Kepulauan 2024. ...

 

State-owned enterprises of Indonesia

Corporations owned by Government of Indonesia The BUMN Untuk Indonesia (SOEs for Indonesia) campaign was launched by the Ministry of State Owned Enterprises in April 2020;[1] this logo was introduced together with a rebranding of the Ministry and the introduction of the AKHLAK core values across all state-owned enterprises effective on 1 July 2020. It replaces the BUMN Hadir Untuk Negeri (SOEs Serving the Nation) campaign, launched in 2016 in conjunction with the Ministry's 18th anniv...

 

小林百太郎

こばやし ひゃくたろう小林 百太郎生誕 1929年2月4日[1][2] 日本 大阪府堺市[1]死没 (2022-03-27) 2022年3月27日（93歳没）[3]出身校 大阪府立機械工業専門学校[2]職業 実業家馬主肩書き FYH株式会社 名誉会長[4]日本馬主協会連合会 元副会長[1]阪神馬主協会元会長[1]親戚 小林 保（兄）小林 福松（兄）小林 義弘（兄）[2]テンプレ�...

راشد سنييف

راشد سنييف (بالتتارية: Рәшит Гали улы Сөнәев)‏  معلومات شخصية الميلاد 1 مارس 1943 (العمر 81 سنة)[1]طشقند  مواطنة الاتحاد السوفيتي روسيا  عضو في الجمعية الملكية،  والأكاديمية الوطنية الألمانية للعلوم ليوبولدينا[2]،  والأكاديمية الوطنية للعلوم،  والأكادي�...

 

Savage River (TV series)

Australian TV series Savage RiverKatherine Langford in a promotional image for the series.GenreCrime dramaWritten by Giula Sandler Belinda Bradley Franz Docherty Directed byJocelyn MoorhouseStarring Katherine Langford Virginia Gay Jacqueline McKenzie Country of originAustraliaOriginal languageEnglishNo. of seasons1No. of episodes6 (list of episodes)ProductionProducersAngie FielderPolly StanifordProduction locationVictoria, AustraliaCinematographyDon McAlpineProduction companyAquarius FilmsOri...