Inzidenzmatrix

Eine Inzidenzmatrix eines Graphen ist eine Matrix, welche die Beziehungen der Knoten und Kanten des Graphen speichert. Wenn der Graph Knoten und Kanten besitzt, ist seine Inzidenzmatrix eine -Matrix. Der Eintrag in der -ten Zeile und -ten Spalte gibt an, ob der -te Knoten Teil der -ten Kante ist. Steht an dieser Stelle eine 1, ist eine Inzidenzbeziehung gegeben, bei einer 0 liegt keine Inzidenz vor. Es wird davon ausgegangen, dass die Knoten von 1 bis und die Kanten von 1 bis durchnummeriert sind.

Definition

Ungerichtete Graphen

Für einen schleifenfreien ungerichteten Graphen mit und ist die Inzidenzmatrix formal definiert durch:

Die Inzidenzmatrix eines ungerichteten Graphen enthält also in jeder Spalte genau 2 von 0 verschiedene Einträge.

Gerichtete Graphen

Für einen schleifenfreien gerichteten Graphen mit und ist die Inzidenzmatrix definiert durch:

wobei hier einen beliebigen Knoten darstellt.

Die Inzidenzmatrix eines gerichteten Graphen enthält also in jeder Spalte genau einmal die (Startknoten) und einmal die (Endknoten). Alternativ werden Inzidenzmatrizen manchmal auch mit umgekehrtem Vorzeichen definiert, das heißt, , falls die Kante am Knoten beginnt, und falls die Kante am Knoten endet. Dies ist insbesondere zu beachten, wenn man Ungleichungen betrachtet, die Inzidenzmatrizen enthalten.

Beispiele

Ungerichtete Graphen

Wir untersuchen nun als Beispiel den rechts stehenden Graphen, der dem Haus vom Nikolaus ähnelt, mit der in dem Bild angegebenen Nummerierung der Knoten und Kanten. Um aus diesem Graphen eine Inzidenzmatrix zu erstellen, beginnen wir mit einer leeren Matrix. Diese enthält für den betrachteten Graphen Spalten und Zeilen. Die Kanten werden in die Spalten eingetragen und die Knoten in die Zeilen.

Die Zahlen an den Kanten sind dabei nicht mit Gewichtungen der Kanten zu verwechseln. Sie beschreiben die Namen der Kanten , die in der Matrix als Spalten wiederzufinden sind.

Nun werden für jede Spalte (Kante) die dazugehörigen Knoten mit 1 markiert, alle anderen Knoten mit 0. Es ergibt sich folgende Inzidenzmatrix:

oder als Tabelle formatiert:

e1 e2 e3 e4 e5 e6
v1 1 0 0 0 1 0
v2 1 1 0 0 0 1
v3 0 1 1 0 0 0
v4 0 0 1 1 0 0
v5 0 0 0 1 1 1

Ist die Inzidenzmatrix eines ungerichteten Graphen korrekt aufgebaut, dann muss in jeder Spalte (Kante) in Summe 2 stehen, da jede Kante exakt 2 Knoten verbindet.

Für nicht-schleifenfreie Graphen wird festgelegt: Ist eine Kante eine Schleife, also eine Kante, die einen Knoten mit sich selbst verbindet, steht in der entsprechenden Zelle eine 2. Die Summe jeder Zeile entspricht der Anzahl Kantenenden an dem Knoten.[1]

Gerichtete Graphen

Als Beispiel einer Inzidenzmatrix eines gerichteten Graphen betrachten wir nun den rechts stehenden Graphen. Wieder nehmen wir die Nummerierung der Knoten als vorgegeben an. Die Kanten sind wie folgend nummeriert: Es ist und . Die Inzidenzmatrix ist also eine -Matrix:

oder als Tabelle formatiert:

e1 e2 e3 e4 e5 e6
v1 1 0 −1 1 0 0
v2 −1 −1 0 0 1 0
v3 0 1 1 0 0 −1
v4 0 0 0 −1 −1 1

Die Inzidenzmatrix eines gerichteten Graphen ist korrekt aufgebaut, wenn in jeder Spalte zwei Nichtnulleinträge stehen, die sich zu Null addieren.

Zusammenhang mit anderen Matrizen

Eine andere Matrix, die Graphen beschreibt, ist die Laplace-Matrix. Es ist eine -Matrix, wobei die Anzahl der Knoten ist. Die Koeffizienten ihrer Diagonale enthalten den Grad der Knoten des Graphen, und die anderen Koeffizienten in Zeile und in Spalte sind gleich −1, wenn die Knoten und verbunden sind, und 0, wenn dies nicht der Fall ist.

Wenn die Inzidenzmatrix eines gerichteten Graphen ist, können wir die Laplace-Matrix durch Multiplizieren von mit seiner transponierten Matrix berechnen:

Zum Beispiel für den gerichteten Graphen in der nebenstehenden Abbildung:

Die Adjazenzmatrix eines Graphen ist eine weitere Matrix, die den Graphen beschreibt. Es ist eine -Matrix, wobei die Anzahl der Knoten ist. Die anderen Koeffizienten in Zeile und in Spalte sind gleich 1, wenn die Knoten und verbunden sind, und ansonsten 0. Für einen ungerichteten Graphen ist diese Matrix symmetrisch.

Die Gradmatrix eines Graphen ist eine -Diagonalmatrix, die den Grad jedes Knotens auflistet. Der Koeffizient in Zeile und in Spalte gibt den Grad des Knoten an, alle anderen Koeffizienten sind 0.

Wenn die Inzidenzmatrix eines ungerichteten Graphen ist, seine Adjazenzmatrix und seine Gradmatrix ist, dann gilt:

Zum Beispiel für den ungerichteten Graphen in der nebenstehenden Abbildung:

Indem wir die Diagonale von den anderen Werten isolieren, erhalten wir:

Der Kantengraph eines ungerichteten Graphen wird erhalten, indem seine Kanten durch Knoten ersetzt werden und die neuen Knoten verbunden werden, wenn die entsprechenden ursprünglichen Kanten einen Knoten gemeinsam haben. Die nebenstehende Abbildung zeigt den Kantengraph des ungerichteten Graphen aus dem vorigen Beispiel.

Wenn die Inzidenzmatrix eines ungerichteten Graphen und die Einheitsmatrix ist, können wir die Adjazenzmatrix seines Kantengraphen folgendermaßen berechnen:

Zum Beispiel für den Kantengraphen in der nebenstehenden Abbildung:

Verwendung

Speicherung von Graphen im Computer

Inzidenzmatrizen werden in der Informatik zur Speicherung von Graphen verwendet. Die Inzidenzmatrix eines Graphen mit Knoten und Kanten benötigt einen Speicherplatz von . Da die Platzkomplexität von Adjazenzmatrizen beträgt, sind Inzidenzmatrizen, sollte es weniger Kanten als Knoten geben, speicherplatztechnisch effizienter.

Spektrale Graphentheorie

Des Weiteren finden Inzidenzmatrizen Anwendung in der spektralen Graphentheorie, wo versucht wird, aufgrund gewisser Eigenschaften der Inzidenzmatrix Rückschlüsse auf die Eigenschaften des repräsentierten Graphen zu ziehen.

Optimierung

Die Inzidenzmatrix eines ungerichteten bipartiten Graphen ist eine total unimodulare Matrix, genauso wie die eines Digraphen. Daher lässt sich unter gewissen Voraussetzungen die Ganzzahligkeit der Lösung eines linearen Optimierungsproblems zeigen, wenn die zulässige Menge durch eine der vorhin genannten Inzidenzmatrizen definiert wird. Insbesondere stellt dies eine Verbindung zwischen diskreter Optimierung und linearer Optimierung her.

Literatur

Einzelnachweise

  1. Manfred Brill: Mathematik für Informatiker. Einführung an praktischen Beispielen aus der Welt der Computer. 2., völlig neu bearbeitete Auflage. Hanser Fachbuchverlag, München u. a. 2005, ISBN 3-446-22802-0, S. 161–169.

Read other articles:

Aon plcJenisPublikKode emitenNYSE: AON (Kelas A)Komponen S&P 500IndustriJasa profesionalDidirikan1982; 42 tahun lalu (1982)PendiriPatrick RyanKantorpusatLondon, Britania RayaWilayah operasiSeluruh duniaTokohkunciLester B. Knight(Chairman)Eric Andersen(Presiden)Greg Case(CEO)JasaKonsultansi ResikoKonsultansi PensiunKonsultansi KesehatanPendapatan US$10 milyar (£8 milyar hingga 2017[update])[1]Laba operasi $1,63 milyar (£1,3 milyar hingga 2017[update])[1&#...

 

Stencil que denuncia la manipulación televisiva. La manipulación de los medios de comunicación consiste en una serie de técnicas relacionadas entre sí con las que miembros de un determinado grupo crean una imagen o una idea que favorece sus intereses particulares.[1]​ Entre estas tácticas destacan las falacias lógicas y la propaganda, que a menudo implican la supresión de información o de otros puntos de vista a través de su distorsión, induciendo a otras personas o grupos de...

 

Prime Minister of Trinidad and Tobago since 2015 For the Australian cyclist, see Keith Rowley (cyclist). The HonourableKeith RowleyMPRowley in 20247th Prime Minister of Trinidad and TobagoIncumbentAssumed office 9 September 2015PresidentAnthony CarmonaPaula-Mae WeekesChristine KangalooPreceded byKamla Persad-Bissessar8th Leader of the Opposition of Trinidad and TobagoIn office4 June 2010 – 9 September 2015Prime MinisterKamla Persad-BissessarPreceded byKamla Persad-BissessarSucc...

Untuk sirup, lihat Molase. Black TreacleLagu oleh Arctic Monkeysdari album Suck It and SeeSisi-BYou & IDipublikasiEMI Music Publishing Ltd.Dirilis23 Januari 2012Format 7 Unduhan musik GenreIndie rockDurasi3:35LabelDominoPencipta Alex Turner Jamie Cook Matt Helders Nick O'Malley ProduserJames FordMusic videoBlack Treacle di YouTube Black Treacle adalah sebuah lagu dari band indie rock Inggris Arctic Monkeys, dirilis sebagai single keempat dari album studio keempat mereka Suck It and See da...

 

Karl Liebknecht Anggota ReichstagMasa jabatan1912–1918 Informasi pribadiLahir(1871-08-13)13 Agustus 1871Leipzig, Kerajaan Sachsen, Kekaisaran JermanMeninggal15 Januari 1919(1919-01-15) (umur 47)Berlin, JermanKewarganegaraanJermanKebangsaanJermanPartai politik Partai Demokrat Sosial Jerman(1900–1916) Liga Spartakus(1914–1918) Partai Komunis Jerman(1919) Suami/istriJulia Paradies (m. 1900; meninggal 1911)Sophie Liebknecht (m. 1914)HubunganWilhelm Liebknecht (ayah)Natalie Liebknecht (...

 

Languages used in the Mediterranean island of Cyprus This article is about the modern languages. For the ancient Pre-Indo-European language, see Eteocypriot language. Languages of CyprusSign in the Sovereign Base Areas of Akrotiri and Dhekelia in English, Greek, and TurkishOfficial Greek Turkish Vernacular Cypriot Greek Cypriot Turkish Minority Armenian (recognised) Cypriot Arabic (recognised) Kurbetcha (unrecognised) Foreign English (76%)[1] French (7%) German (5%) Signed Greek Sign ...

Streaming and linear television service Curiosity StreamType of siteVideo on demandLinear broadcast television channelAvailable inEnglishTraded asNasdaq: CURIFoundedMarch 18, 2015; 9 years ago (2015-03-18)HeadquartersSilver Spring, Maryland, United StatesArea servedWorldwideFounder(s)John S. HendricksKey people Clint Stinchcomb (President & CEO) Tia Cudahy (COO & General Counsel) Peter Westley (CFO) Revenue US$39.6 million (2020)[1]UR...

 

BMW MotorradJenis produkMerek sepeda motorPemilikBMWDiluncurkan1923PasarDi seluruh duniaSitus webwww.bmw-motorrad.com BMW Motorrad adalah merek dan divisi pabrikan sepeda motor otomotif Jerman, BMW.[1] Ini telah memproduksi sepeda motor sejak 1923, dan mencapai rekor penjualan untuk tahun kelima berturut-turut pada tahun 2015. Dengan total 136.963 kendaraan terjual pada tahun 2015, BMW mencatat pertumbuhan penjualan sebesar 10,9% dibandingkan dengan tahun 2014.[2] Pada Mei 201...

 

Nick Taylor2012 Australian Paralympic team portrait of TaylorPersonal informationNationality AustraliaBorn (1980-01-18) 18 January 1980 (age 44)SportCountryAustraliaSportWheelchair basketballEventMen's teamCollege teamUniversity of Texas at ArlingtonTeamWollongong Roller HawksTurned pro2005 Medal record Wheelchair basketball Paralympic Games 2012 London Men's wheelchair basketball World Championship 2014 Incheon Team Nick Taylor (born 18 January 1980) is a wheelchair basketball pla...

Mahan-class destroyer For other ships with the same name, see USS Shaw. USS Shaw (DD-373), September 1938 History United States NamesakeCaptain John Shaw BuilderPhiladelphia Naval Shipyard Laid down1 October 1934 Launched28 October 1935 Commissioned18 September 1936 Decommissioned2 October 1945 Stricken4 October 1945 FateScrapped July 1946 General characteristics Class and typeMahan-class destroyer Displacement1,450 long tons (1,470 t) Length341.3 ft (104.0 m) Beam34.7 ft ...

 

Economy of Byzantine Empire Parable of the Workers in the Vineyard. Workers on the field (down) and pay time (up), Byzantine Gospel of 11th century. Byzantine culture Aristocracy and bureaucracy Army Art Architecture Calendar Cities Coinage Cuisine Dance Diplomacy Dress Economy Gardens Law Literature Medicine Music People Science vte The Byzantine economy was among the most robust economies in the Mediterranean for many centuries. Constantinople was a prime hub in a trading network that at va...

 

Neighborhood of Chittagong, Bangladesh Faujdarhat Railway Station Faujdarhat is a neighborhood of Chittagong City in Bangladesh. It is well known as a ship breaking area, with one of the largest breaking yards in the world: Chittagong Ship Breaking Yard. There are several institutions including Faujdarhat Cadet College, the first cadet college in Bangladesh.[1] History In 1995, the Forest Department created a 5 square kilometres (1.9 sq mi) mangrove forest park that stretche...

Santo RomualdusAbbasLahirskt. 951RavennaMeninggal19 Juni 1027Val di CastroDihormati diGereja Ortodoks TimurGereja Katolik RomaPesta19 Juni7 Februari (1595–1969) Romuald (bahasa Latin: Romualdus; skt. 951 – secara tradisional 19 Juni, skt. 1025/27 M)[1] merupakan pendiri ordo Camaldolese dan seorang tokoh utama dalam Renaisans pertapaan Eremit dari abad kesebelas.[2] Catatan ^ The traditional year of his death, given as 1027, rests entirely on testimony by Guido Grandi ...

 

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 Februari 2023. Invasi DiliBagian dari Integrasi Timor TimurTanggal7 Desember 1975LokasiDili, Timor TimurHasil Kemenangan IndonesiaPihak terlibat  Indonesia Timor TimurTokoh dan pemimpin Soeweno Paulino GamaKekuatan Invasi awal~1,0004 kapal perangPekan-pekan ber...

 

Disambiguazione – Amasi rimanda qui. Se stai cercando altri significati, vedi Amasi (disambigua). Questa voce o sezione sull'argomento sovrani è priva o carente di note e riferimenti bibliografici puntuali. Sebbene vi siano una bibliografia e/o dei collegamenti esterni, manca la contestualizzazione delle fonti con note a piè di pagina o altri riferimenti precisi che indichino puntualmente la provenienza delle informazioni. Puoi migliorare questa voce citando le fonti più pr...

American baseball player (born 1988) Baseball player Andrew LamboLambo with the Great Lakes Loons in 2008Outfielder/First basemanBorn: (1988-08-11) August 11, 1988 (age 35)Newbury Park, California, U.S.Batted: LeftThrew: LeftMLB debutAugust 13, 2013, for the Pittsburgh PiratesLast MLB appearanceApril 7, 2016, for the Oakland AthleticsMLB statisticsBatting average.189Hits18Home runs1Runs batted in3 Teams Pittsburgh Pirates (2013–2015) Oakland Athletics (201...

 

Stinger Stinger system Jenis Manportable surface-to-air missile Negara asal United States Sejarah pemakaian Masa penggunaan 1981–Present Digunakan oleh See Operators Pada perang Falklands War, Soviet invasion of Afghanistan, Angolan Civil War, Kargil War, Yugoslav Wars Sejarah produksi Perancang General Dynamics Tahun 1967 Produsen Raytheon Missile Systems Biaya produksi US$38,000 Diproduksi 1978 Varian FIM-92A, FIM-92B, FIM-92C, FIM-92D, FIM-92G Spesifikasi (FIM-9...

 

Alberto BigonBigon al Milan nella stagione 1972-73Nazionalità Italia Altezza180 cm Peso73 kg Calcio RuoloAllenatore (ex centrocampista, attaccante) Termine carriera1º luglio 1984 - giocatore4 novembre 2009 - allenatore CarrieraGiovanili 1962-1966 Padova Squadre di club1 1964-1967 Padova64 (15)1967 Napoli0 (0)1967-1969 SPAL49 (10)1969-1971 Foggia65 (18)1971-1980 Milan218 (56)1980-1982 Lazio57 (12)1982-1984 L.R. Vicenza57 (16) Nazionale 1967 Italia...

Questa voce sull'argomento nobili italiani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Ducato di MilanoCasato degli Sforza Francesco I Figli Galeazzo Maria Ippolita Maria Filippo Maria Sforza Maria Ludovico Maria Elisabetta Maria Ascanio Maria Ottaviano Maria Fiordelisa Maria Sforza Secondo, figlio naturale Polissena, figlia naturale Drusiana, figlia naturale Tristano, figlio naturale Galeazzo Maria Figli Gian Galeazzo Maria Ermes Maria Bianca Mar...

 

У этого термина существуют и другие значения, см. Туркестан. ГородТуркестанказ. Түркістан,латиница — каз. Türkıstan Мавзолей Ходжи Ахмеда Ясави Герб 43°18′00″ с. ш. 68°14′37″ в. д.HGЯO Страна  Казахстан Область Туркестанская Акимат Туркестан Аким Турашбеков, Нурбо�...