スペクトルグラフ理論

数学において、スペクトルグラフ理論は、隣接行列もしくはラプラシアン行列のような、そのグラフに結びついた行列の固有方程式、固有値、固有ベクトルに関係する、グラフの性質の研究である。

単純グラフの隣接行列は、実な対称行列であり、したがって直行行列に対角化可能（英語版）であり；その固有値は実な代数的整数である。

頂点の名称付けによってその隣接行列が変わるのにたいして、それのスペクトルは、完全ではないものの、ひとつのグラフの不変量（英語版）である。

スペクトルグラフ理論は、コラン・ド・ウェルディール数（英語版）のような、そのグラフと結びついた行列の固有値の重複度を通して定義される、グラフのパラメーターとも関係する。

共スペクトルグラフ

もし二つのグラフの隣接行列の固有値の多重集合が等しいならば、それらの二つのグラフは共スペクトル（英: cospectral）あるいは等スペクトル（英: isospectral）であると呼ばれる。

あり得る最も小さな多面体グラフの、二つの等スペクトルな九面体（英語: enneahedron）。

二つの共スペクトルグラフは互いに同型である必要はない、しかし同型なグラフは常に共スペクトルである。

共スペクトルグラフを探すこと

ほとんどすべての木は共スペクトルである、すなわち、頂点が増えるにつれ、共スペクトルな木があるような木の割合は1に近づいてゆく。[1]

正則グラフの一対は、それらの補グラフが共スペクトルであるときにかぎり、共スペクトルである。[2]

もしそれらが等しい交点配列（英: inter-section array）を有するときに限り、一対の距離正則グラフ（英語: distance-regular graph）は共スペクトルである。

共スペクトルグラフは砂田の方法（英語版）によっても構成されうる。[3]

共スペクトルグラフのその他の重要な根拠としては点と直線の幾何（英語版）の、点-共線形グラフ（英: point-colinearity graph）と直線-交点グラフ英: line-intersection graphがある。これらのグラフは常に共スペクトルである、しかししばしばグラフ同型ではない。[4]

関連項目

脚注または引用文献

  1. ^ Schwenk (1973).
  2. ^ Godsil (2007).
  3. ^ Sunada (1985).
  4. ^ 外部リンクの(Brouwer & Haemers 2011)を見よ。

ウェブサイト

書籍

  • Schwenk, A. J. (1973). “Almost All Trees are cospectral”. In Harary, Frank. New Directions in the Theory of Graphs. New York: Academic Press. p. 275-307. ISBN 012324255X. OCLC 890297242 
  • 吉田 悠一：「スペクトルグラフ理論: 線形代数からの理解を目指して」、サイエンス社(SGCライブラリ190），ISBN 978-4781916019、（2024年3月）.
  • ボグダン・ニカ：「線形代数で考える スペクトラル・グラフ理論入門」、日本評論社、ISBN 978-4535790049、（2024年4月）.

雑誌

参考文献

外部リンク

Read other articles:

Peternakan babi

Pertanian Umum Agribisnis Agroindustri Agronomi Ilmu pertanian Jelajah bebas Kebijakan pertanian Lahan usaha tani Mekanisasi pertanian Menteri Pertanian Perguruan tinggi pertanian Perguruan tinggi pertanian di Indonesia Permakultur Pertanian bebas ternak Pertanian berkelanjutan Pertanian ekstensif Pertanian intensif Pertanian organik Pertanian urban Peternakan Peternakan pabrik Wanatani Sejarah Sejarah pertanian Sejarah pertanian organik Revolusi pertanian Arab Revolusi pertanian Inggris Revo...

 

Daftar akun Facebook dengan pengikut terbanyak

Cristiano RonaldoDaftar berikut ini berisi akun dengan jumlah pengikut terbesar di jejaring media sosial Facebook.[1][2] Peringkat Nama akun Pengikut(juta) Negara 1 Facebook 213  USA 2 Samsung 159  KOR 3 Cristiano Ronaldo 122  POR 4 Real Madrid C.F. 109  ESP 5 Coca-Cola 107  USA 6 FC Barcelona 102  ESP 7 Shakira 101  COL 8 Vin Diesel 98  USA 9 Tasty 96  USA 10 Lionel Messi 89  ARG 11 Eminem 88  USA 12 YouTube 83  USA ...

 

Pontault-Combault

Peta infrastruktur dan tata guna lahan di Komune Pontault-Combault.  = Kawasan perkotaan  = Lahan subur  = Padang rumput  = Lahan pertanaman campuran  = Hutan  = Vegetasi perdu  = Lahan basah  = Anak sungaiPontault-CombaultNegaraPrancisArondisemenTorcyKantonPontault-CombaultAntarkomunebelum ada pada 2005Kode INSEE/pos77373 /  Pontault-Combault merupakan sebuah komune di pinggiran timur Paris, Prancis. Terletak 19.8 km (12.3 mil) dari pusat kot...

Kayakapı

Neighbourhood of Ürgüp, Turkey This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help to improve this article by introducing more precise citations. (August 2016) (Learn how and when to remove this template message) Kayakapi NeighbourhoodTurkish: Kayakapı MahallesiPanoramic view over KayakapiShown within TurkeyLocationÜrgüp, TurkeyRegionCentral Anatolia RegionCoordinates38°38′05″N ...

 

بطولة ويمبلي الدولية

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (أبريل 2022) بطولة ويمبلي الدولية سنة التأسيس 1988 النادي الأكثر نجاحاً أرسنال وسامبدوريا (3 ألقاب لكل منهما) تعديل مصدري...

 

Quoll

Genus of marsupial mammals QuollTemporal range: Late Miocene – Recent[1] PreꞒ Ꞓ O S D C P T J K Pg N Eastern quoll (Dasyurus viverrinus) Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Mammalia Infraclass: Marsupialia Order: Dasyuromorphia Family: Dasyuridae Subfamily: Dasyurinae Tribe: Dasyurini Genus: DasyurusÉ. Geoffroy, 1796 Type species Didelphis maculataAnon., 1791(=Dasyurus viverrinus Shaw, 1800) Species Dasyurus albopunctatus Dasyur...

Warragamba, New South Wales

Town in New South Wales, AustraliaWarragambaNew South WalesWarragambaCoordinates33°53′30″S 150°36′12″E / 33.89167°S 150.60333°E / -33.89167; 150.60333Population1,241 (2016 census)[1]Postcode(s)2752Elevation178 m (584 ft)Location69 km (43 mi) W of SydneyLGA(s)Wollondilly ShireState electorate(s)WollondillyFederal division(s)Hume Localities around Warragamba: Megalong Valley Megalong Valley Wallacia Megalong Valley Warragamba...

 

Молитва за Украину

Молитва за Украинуукр. Дитячий гімн Гимн Дата создания 1885 Дата выпуска 1885 Жанр гимн Язык украинский Композитор Николай Лысенко Автор слов Александр Конисский  Медиафайлы на Викискладе «Молитва за Украину» (укр. Молитва за Україну) — торжественная песня, известная ...

 

Columbus Square (New York City)

Five buildings in Manhattan, New York City 805 Columbus Avenue 795 Columbus Avenue 775 Columbus Avenue 65 West 96th Street Columbus Square consists of five luxury rental buildings located in the Upper West Side of Manhattan, in New York City. The real estate development runs from 97th Street to 100th Street between Columbus Avenue and Amsterdam Avenue, with over 300,000 square feet (28,000 m2) of retail space. Initially known as Columbus Village, the five buildings include: 808 Columbus ...

Gongzhuling

County-level & Sub-prefectural city in Jilin, People's Republic of ChinaGongzhuling 公主岭市County-level & Sub-prefectural cityGongzhulingLocation in Jilin provinceCoordinates (Gongzhuling government): 43°30′19″N 124°49′21″E / 43.5053°N 124.8224°E / 43.5053; 124.8224CountryPeople's Republic of ChinaProvinceJilinPrefecture-level cityChangchun[1]SeatDongsan SubdistrictArea[2] • County-level & Sub-prefectural cit...

 

Rio Bravo, Texas

City in Texas, United StatesRio BravoCityCoordinates: 27°21′53″N 99°28′46″W / 27.36472°N 99.47944°W / 27.36472; -99.47944CountryUnited StatesStateTexasCountyWebbGovernment • TypeMayor • MayorGilbert Aguilar JrArea[1] • City0.67 sq mi (1.72 km2) • Land0.65 sq mi (1.68 km2) • Water0.02 sq mi (0.04 km2)  1.4% • Metro161.76 sq&...

 

Executive Committee of Gagauzia

An editor has nominated this article for deletion.You are welcome to participate in the deletion discussion, which will decide whether or not to retain it.Feel free to improve the article, but do not remove this notice before the discussion is closed. For more information, see the guide to deletion.Find sources: Executive Committee of Gagauzia – news · newspapers · books · scholar · JSTOR%5B%5BWikipedia%3AArticles+for+deletion%2FExecutive+Committee+of+...

Повітряні сили Національної гвардії Аляски

Повітряні сили Національної гвардії Аляски Alaska Air National Guard Емблема повітряних сил Національної гвардії АляскиНа службі 15 вересня 1952Країна  СШАНалежність Повітряні сили Національної гвардії СШАВид ПС СШАТип повітряний компонент забезпечення Національної гвардії шт...

 

Compagnie du Chemin de fer Pau–Oloron–Mauléon et du Tramway de Bayonne à Biarritz

Die Compagnie du Chemin de fer de Pau–Oloron–Mauléon et du Tramway de Bayonne à Biarritz (POM) betrieb das größte Lokalbahnnetz im Département Basses-Pyrénées. Aktie über 100 Francs der Compagnie du chemin de fer de Pau-Oloron-Mauléon et du tramway de Bayonne à Biarritz vom 1. Januar 1911 Im Jahr 1888 eröffnete die 1883 unter dem Namen Chemins de fer à voie étroite du Midi gegründete Gesellschaft, die sich seit 1887 Compagnie des Tramways de Bayonne au Lycée et à Biarritz ...

 

Synonyme (taxinomie)

Pour les articles homonymes, voir Synonymie. Le vampire des abysses Vampyroteuthis infernalis Chun, 1903 admet de nombreux synonymes :• Cirroteuthis macrope Berry, 1911• Vampyroteuthis macrope Berry, 1911• Melanoteuthis lucens Joubin, 1912• Watasella nigra Sasaki (en), 1920• Danateuthis schmidti Joubin, 1929• Hansenoteuthis lucens Joubin, 1929• Melanoteuthis schmidt Joubin, 1929• Melanoteuthis beebei Robson, 1929• Retroteuthis pacifica Joubin, 1929• Melanoteuthi...

LVTP-5裝甲車

LVTP-5 LVTP-5类型兩棲裝甲運兵車原产地 美国服役记录服役期间1952-参与战争／衝突1958年黎巴嫩危機越戰生产历史研发者博格華納研发日期1950-1951制造数量1124基本规格重量37.4公噸长度9.04公尺宽度3.57公尺高度2.92公尺操作人数3+34 乘員装甲6-16公厘的鋼質裝甲主武器M1919A4機槍(A、A1)、白朗寧M2重機槍(A1與其他款式)、M240通用機槍(LVTH-6)、M49 24倍徑105mm榴彈炮(LVTH-6)、工蜂四型(LVTP-...

 

Archery at the 2008 Summer Olympics

Archeryat the Games of the XXIX OlympiadVenueOlympic Green Archery FieldDates9–15 August 2008No. of events4 (2 men, 2 women)Competitors128 from 49 nations← 20042012 → Part of a series on Archery at the 2008 Summer Olympics Events Individual menwomen Team menwomen vte At the 2008 Summer Olympics, the Archery competitions were held between 9 August and 15 August, at the Olympic Green Archery Field, a temporary venue on the Olympic Green, Beijing's Olympic Park...

 

Il ventaglio di Lady Windermere

Disambiguazione – Se stai cercando il film del 1916, vedi Lady Windermere's Fan (film 1916). Disambiguazione – Se stai cercando il film del 1925, vedi Il ventaglio di Lady Windermere (film). Il ventaglio di Lady WindermereCommedia in quattro atti AutoreOscar Wilde Titolo originaleLady Windermere's Fan Lingua originaleInglese GenereCommedia Composto nel1892 Prima assoluta20 febbraio 1892St James's Theatre, Londra Personaggi Lord Windermere Lord Darlington Lord Augustus Lorton Mr Dumby Mr ...

Naim Süleymanoğlu

Naim Süleymanoğlu halterofilismo Representante Bulgária (até 1986)Turquia (a partir de 1986) Nascimento 23 de janeiro de 1967Ptitchar, Bulgária Nacionalidade turca Morte 18 de novembro de 2017 (50 anos)Istambul, Turquia Compleição Peso: 56-64 kg • Altura: 1,47 m Medalhas Jogos Olímpicos Ouro Seul 1988 –60 kg Ouro Barcelona 1992 –60 kg Ouro Atlanta 1996 –64 kg Campeonatos mundiaisTotal Ouro Södertälje 1985 –60 kg Ouro Sófia 1986 –60 kg Ouro Atenas 1989 –60 k...

 

Princes of Orléans

The Princes of Orléans were male-line descendants of the House of Orléans headed by the Duke of Orléans. The present House of Orléans was founded by Philippe de France, duc d'Orléans, known as Monsieur and the only sibling of Louis XIV of France. The children of Philippe de France held the rank of 'Grandchildren of France', being male-line descendants of Louis XIII of France, the father of Louis XIV and Monsieur. This allowed that group of people the style of Royal Highness; this was fro...