Spektrum (Graphentheorie)

Das Spektrum dient in der Graphentheorie zur Untersuchung der Eigenschaften von Graphen. Das entsprechende Gebiet wird als Algebraische Graphentheorie oder Spektrale Graphentheorie bezeichnet. Die Berechnung des Spektrums eines Graphen ermöglicht einen sehr effektiven Algorithmus zum Graphenzeichnen (Hall’s Algorithmus.) Auch Expandergraphen können mittels spektraler Methoden charakterisiert werden.

Definition

Als Spektrum eines Graphen bezeichnet man die (nach Größe geordnete) Folge der Eigenwerte seiner Adjazenzmatrix. Letztere werden auch als Eigenwerte des Graphen bezeichnet.

(Ungerichtete Graphen haben eine symmetrische Adjazenzmatrix und deshalb reelle Eigenwerte.)

Graph Adjazenzmatrix Eigenwerte

Häufig werden auch die Eigenwerte der Laplace-Matrix des Graphen als sein Spektrum bezeichnet.

Beispiele

Die folgenden Beispiele beziehen sich auf das Spektrum der Adjazenzmatrix.

  • Der vollständige Graph auf Knoten hat das Spektrum
    .
  • Der vollständig bipartite Graph hat das Spektrum
    .
  • Ein Graph ist genau dann bipartit, wenn sein Spektrum symmetrisch bzgl. ist.
  • Der größte Eigenwert eines -regulären Graphen ist (Satz von Frobenius), seine Vielfachheit ist die Anzahl der Zusammenhangskomponenten des Graphen.

Literatur

  • Dragoš M. Cvetković, Michael Doob, Horst Sachs: Spectra of graphs. Theory and applications. Third edition. Johann Ambrosius Barth, Heidelberg 1995, ISBN 3-335-00407-8.
  • Norman Biggs: Algebraic graph theory. Second edition. Cambridge Mathematical Library. Cambridge University Press, Cambridge 1993, ISBN 0-521-45897-8.
  • Chris Godsil, Gordon Royle: Algebraic graph theory (Graduate Texts in Mathematics, 207). Springer-Verlag, New York 2001, ISBN 0-387-95241-1; 0-387-95220-9.

Read other articles:

Aneka macam pinset. Pinset atau cunam (serapan dari Belanda: pincetcode: nl is deprecated ) adalah perkakas tangan yang digunakan untuk menjepit benda terlalu kecil yang susah dipegang dan digenggam dengan jari manusia. Pinset berbentuk penjepit kecil yang umumnya digerakkan oleh ibu jari dan telunjuk. Benda ini kemungkinan besar ditiru dari pencapit yang digunakan untuk mengambil atau menahan benda panas.[1] Istilah Kata pinset merupakan serapan dari bahasa Belanda: pincet (pelafalan...

 

Tatang Kurniadi Informasi pribadiLahir3 April 1946 (umur 77)Soreang, Bandung, Jawa BaratSuami/istriHj. Retno Estiningsih, S.H.Alma materAkademi Angkatan Udara (1970)Karier militerPihak IndonesiaDinas/cabang TNI Angkatan UdaraMasa dinas1970—2002Pangkat Marsekal Muda TNISatuanKorps PenerbangSunting kotak info • L • B Marsekal Muda TNI (Purn.) Entjep Tatang Kurniadi, PSC., S.H., M.M. (lahir 3 April 1946) adalah seorang Purnawirawan TNI-AU yang terakhir menjabat Ang...

 

Пейтингерова скрижаль XIII века, копия с древнеримской карты Картогра́фия (от греч. χάρτης «бумага из папируса» + γράφειν «рисовать») — наука об исследовании, моделировании и отображении пространственного расположения, сочетания и взаимосвязи объектов, явлений природ�...

Halaman ini berisi artikel tentang laksamana armada Rusia. Untuk pakar iktiologi Rusia, lihat Vladimir V. Tchernavin. Vladimir ChernavinChernavin (2013)Lahir(1928-04-22)22 April 1928Mykolaiv, SSR Ukraina, Uni SovietMeninggal18 Maret 2023(2023-03-18) (umur 94)Moskow, RusiaPengabdian Uni SovietDinas/cabang Angkatan Laut Uni SovietLama dinas1944–1992PangkatLaksamana ArmadaKomandanArmada UtaraAngkatan Laut Uni SovietAngkatan Laut Persemakmuran Negara-negara IndependenPerang/...

 

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

 

Wacken Open AirSimbol resmi Wacken Open AirJenisFestival musik Heavy metalDeath metalThrash metalFrekuensiTahunanLokasiWacken, Schleswig-HolsteinKoordinat54°01′42″N 9°21′22″E / 54.02833°N 9.35611°E / 54.02833; 9.35611NegaraJermanTahun aktif1990–sekarangAcara pertama24–25 Agustus 1990 (1990-08-25)Pendiri Thomas Jensen Holger Hübner Situs webSitus web resmi Wacken Open Air ( /ˈvɑːkən/, gaya penulisan W:O:A) adalah festival musik heavy metal yang...

American Female Clinical Psychologist This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) The topic of this article may not meet Wikipedia's notability guideline for biographies. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot...

 

MGN beralih ke halaman ini. Untuk perusahaan media Britania Raya yang salah satu pendahulunya bernama Mirror Group Newspapers, lihat Reach plc. Metro Globe NetworkDiluncurkan23 November 2021; 2 tahun lalu (2021-11-23)PemilikPT Mitra Siaran Digital (Media Group)SloganCapture The FutureSebelumnya: Capture Toward FutureNegaraIndonesiaBahasaBahasa InggrisKantor pusatGedung Media Group, Jl. Pilar Mas Raya Kav. A-D Kedoya Selatan, Kebon Jeruk, Jakarta Barat, DKI JakartaSaluran seindukMetroTV ...

 

Subordinate element of U.S. Marine Corps 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: Mountain Warfare Training Center – news · newspapers · books · scholar · JSTOR (December 2021) (Learn how and when to remove this template message) Mountain Warfare Training Center, MWTCMono County, northwest of Bridgepo...

Gereja di Rossosh Eparki Rossosh adalah sebuah eparki Gereja Ortodoks Rusia yang terletak di Rossosh, Federasi Rusia. Eparki tersebut didirikan pada tahun 2013.[1] Referensi ^ http://www.patriarchia.ru/db/text/3478892.html lbsKeuskupan Gereja Ortodoks RusiaPatriark MoskwaEparki di Rusia Abakan dan Khakassia Akhtubinsk Alapayevsk Alatyr Alexdanrov Almetyevsk Amur Anadyr Ardatov Arkhangelsk Armavir Arsenyev Astrakhan Balashov Barnaul Barysh Belgorod Belyov Bezhetsk Birobidzhan Birsk Biy...

 

Overview of the aging of wine Bottles of wine aging in an underground cellar The aging of wine is potentially able to improve the quality of wine. This distinguishes wine from most other consumable goods. While wine is perishable and capable of deteriorating, complex chemical reactions involving a wine's sugars, acids and phenolic compounds (such as tannins) can alter the aroma, color, mouthfeel and taste of the wine in a way that may be more pleasing to the taster. The ability of a wine to a...

 

Swedish heavy metal band For the Welsh rock band, see Catatonia (band). KatatoniaKatatonia at Kavarna Rock Fest 2011, BulgariaBackground informationOriginStockholm, SwedenGenres Heavy metal progressive rock progressive metal doom metal gothic rock death-doom (early) Years active 1991–1994 1996–2018 2019–present Labels Avantgarde Music No Fashion Peaceville Vic Napalm Records Spinoffs October Tide Bloodbath MembersJonas RenkseAnders NyströmNiklas SandinDaniel MoilanenRoger ÖjerssonPast...

Questa voce sull'argomento videogiochi strategici è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Battleground 9: ChickamaugavideogiocoPiattaformaMicrosoft Windows Data di pubblicazione1999 GenereStrategia a turni TemaGuerra di secessione americana OrigineStati Uniti SviluppoTalonSoft PubblicazioneTalonSoft Modalità di giocoGiocatore singolo, multigiocatore(2) Periferiche di inputMouse, tastiera SupportoCD-ROM Requisiti di sistemaPentium 166 MHz (200...

 

Radio station in Monte Rio, California KVRVMonte Rio, CaliforniaBroadcast areaSanta Rosa, CaliforniaFrequency97.7 MHzBranding97.7 The RiverProgrammingFormatClassic rockAffiliationsUnited Stations Radio NetworksOwnershipOwnerLawrence Amaturo(Amaturo Sonoma Media Group, LLC)Sister stationsKFGY, KHTH, KSRO, KWVF, KZSTHistoryFirst air dateNovember 20, 1977 (as KRJB)Former call signsKRJB (1977–1986)KKBR (1/7/1986-1/16/1986)KMGG (1986–2003)Call sign meaningK V RiVerTechnical informationFacility...

 

محمد سعيد هيرسي مورغان   وزير الدفاع في جمهورية الصومال في المنصب1990 – 26 يناير 1991 الرئيس محمد سياد بري معلومات شخصية الميلاد سنة 1949 (العمر 74–75 سنة)  مواطنة الصومال  الحياة العملية المهنة سياسي  الخدمة العسكرية الولاء الصومال  تعديل مصدري - تعديل   محمد سعيد ...

馬爾代夫奧林匹克委員會馬爾代夫奧林匹克委員會會徽成立時間1985年總部馬爾代夫馬累主席Ibrahim Ismail Ali網站https://www.olympic.mv/奥林匹克委员会信息國家或地區 馬爾地夫IOC編碼MDV加入IOC1985年区域组织亞洲奧林匹克理事會 馬爾代夫奧林匹克委員會(Maldives Olympic Committee)是馬爾代夫的國家奧林匹克委員會。該組織成立於1985年,是國際奧委會和亞洲奧林匹克理事會的成員�...

 

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 Januari 2023. Duta Besar Republik Rakyat Tiongkok untuk Sudan Selatan (Hanzi: 中华人民共和国驻南苏丹共和国大使) adalah perwakilan tertinggi dari Republik Rakyat Tiongkok untuk Sudan Selatan. Satu orang telah menduduki posisi ini sejak kedua negar...

 

Boxing competition International sporting eventMen's lightweight at the 2011 Pan American GamesVenueExpo Guadalajara ArenaDatesOctober 22–29Competitors11 from 11 nationsMedalists Yasniel Toledo  Cuba Robson Conceição  Brazil Angel Suarez  Puerto Rico Angel Gutierrez  Mexico«2007 2015» Boxing at the2011 Pan American GamesLight flyweightmenFlyweightmenwomenBantamweightmenLightweightmenLight welterweightmenwomenWelt...

FantasticGenreKomedi romantis, DramaPemeranJoo Sang-wook Kim Hyun-joo Park Si-yeon Ji SooNegara asalKorea SelatanBahasa asliKoreaJmlh. episode16ProduksiDurasi80 hingga 90 menitRumah produksiAStory Co., Ltd.Rilis asliJaringanJTBCRilis2 September (2016-09-02) –22 Oktober 2016 (2016-10-22) Fantastic (Hangul: 판타스틱; RR: Pantaseutik) adalah serial televisi Korea Selatan tahun 2016 yang dibintangi Kim Hyun-joo dan Joo Sang-wook sebagai pemeran utama. D...

 

北日本放送株式会社Kitanihon Broadcasting Co., Ltd. 北日本放送本社社屋種類 株式会社略称 KNB本社所在地 日本〒930-8585[1]富山県富山市牛島町10番18号[1] 北緯36度42分17.3秒 東経137度12分51.3秒 / 北緯36.704806度 東経137.214250度 / 36.704806; 137.214250設立 1952年3月14日[1]業種 情報・通信業法人番号 3230001000758 事業内容 放送法による基幹放送事業 放送に関す...