Graph operations

In the mathematical field of graph theory, graph operations are operations which produce new graphs from initial ones. They include both unary (one input) and binary (two input) operations.

Unary operations

Unary operations create a new graph from a single initial graph.

Elementary operations

Elementary operations or editing operations, which are also known as graph edit operations, create a new graph from one initial one by a simple local change, such as addition or deletion of a vertex or of an edge, merging and splitting of vertices, edge contraction, etc. The graph edit distance between a pair of graphs is the minimum number of elementary operations required to transform one graph into the other.

Advanced operations

Advanced operations create a new graph from an initial one by a complex change, such as:

Binary operations

Binary operations create a new graph from two initial graphs G1 = (V1, E1) and G2 = (V2, E2), such as:

  • graph union: G1 ∪ G2. There are two definitions. In the most common one, the disjoint union of graphs, the union is assumed to be disjoint. Less commonly (though more consistent with the general definition of union in mathematics) the union of two graphs is defined as the graph (V1 ∪ V2, E1 ∪ E2).
  • graph intersection: G1 ∩ G2 = (V1 ∩ V2, E1 ∩ E2);[1]
  • graph join: . Graph with all the edges that connect the vertices of the first graph with the vertices of the second graph. It is a commutative operation (for unlabelled graphs);[2]
  • graph products based on the cartesian product of the vertex sets:
  • graph product based on other products:
  • series–parallel graph composition:
    • parallel graph composition: it is a commutative operation (for unlabelled graphs),
    • series graph composition: it is a non-commutative operation,
    • source graph composition: it is a commutative operation (for unlabelled graphs);
  • Hajós construction.

Notes

  1. ^ Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics. Springer. p. 29. ISBN 978-1-84628-969-9.
  2. ^ a b c Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
  3. ^ Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Entropy waves, the zig-zag graph product, and new constant-degree expanders". Annals of Mathematics. 155 (1): 157–187. arXiv:math/0406038. doi:10.2307/3062153. JSTOR 3062153. MR 1888797.
  4. ^ Frucht, Robert; Harary, Frank (1970). "On the corona of two graphs". Aequationes Mathematicae. 4: 322–324. doi:10.1007/bf01844162. hdl:2027.42/44326.

Read other articles:

Kebutaan

Buta beralih ke halaman ini. Untuk makhluk berukuran besar, lihat Raksasa. Konten dan perspektif penulisan artikel ini tidak menggambarkan wawasan global pada subjeknya. Silakan bantu mengembangkan atau bicarakan artikel ini di halaman pembicaraannya, atau buat artikel baru, bila perlu. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Ada usul agar Tuna netra digabungkan ke artikel ini. (Diskusikan) Ada usul agar artikel ini digabungkan ke Gangguan penglihatan. (Diskusikan)...

 

Keuskupan San Marco Argentano-Scalea

Keuskupan San Marco Argentano-ScaleaDioecesis Sancti Marci Argentanensis-ScaleensisKatolik Katedral di San Marco ArgentanoLokasiNegaraItaliaProvinsi gerejawiCosenza-BisignanoStatistikLuas1.148 km2 (443 sq mi)Populasi- Total- Katolik(per 2014)115.600 (perkiraan)112,600 (perkiraan) (97.4%%)Paroki64Imam74 (diosesan)2 (Ordo Relijius)InformasiDenominasiKatolik RomaRitusRitus LatinPendirian1179KatedralKatedral Santo NikolasPelindungMarkus PenginjilKepemimpinan kin...

 

Keuskupan Agung Ende

Keuskupan Agung EndeArchidioecesis EndehenaKatolik Gereja Katedral EndeLokasiNegaraIndonesiaWilayah Pulau Flores bagian tengah, Nusa Tenggara Timur Kabupaten EndeKabupaten NagekeoKabupaten Ngada Provinsi gerejawiEndeSufraganDenpasarLarantukaMaumereRutengKevikepanEndeBajawaMbayKantor pusatKompleks Misi Ndona, Jl. Jurusan, Desa Onelako, Kec. Ndona, Kab. Ende 86360Koordinat8°50′43″S 121°38′46″E / 8.845314°S 121.646106°E / -8.845314; 121.646106StatistikLua...

Perang Salib Pertama

Perang Salib PertamaBagian dari Perang SalibDirebutnya Yerusalem menandai keberhasilan Perang Salib PertamaTanggal1096–1099LokasiSebagian besar di Levant dan AnatoliaHasil Kemenangan tentara salibPerubahanwilayah Direbutnya YerusalemPembentukan Kerajaan Yerusalem dan negara-negara Tentara Salib lainnyaPihak terlibat Kerajaan Prancis Blois Toulouse Boulogne Flandria Kerajaan Inggris Normandia Le Puy-en-Velay Vermandois Bretagne Republik Genoa Kerajaan Armenia Kilikia County Sisilia Taranto K...

 

Salat Qasar

Bagian dari seriIslam Rukun Iman Keesaan Allah Malaikat Kitab-kitab Allah Nabi dan Rasul Allah Hari Kiamat Qada dan Qadar Rukun Islam Syahadat Salat Zakat Puasa Haji Sumber hukum Islam al-Qur'an Sunnah (Hadis, Sirah) Tafsir Akidah Fikih Syariat Sejarah Garis waktu Muhammad Ahlulbait Sahabat Nabi Khulafaur Rasyidin Khalifah Imamah Ilmu pengetahuan Islam abad pertengahan Penyebaran Islam Penerus Muhammad Budaya dan masyarakat Akademik Akhlak Anak-anak Dakwah Demografi Ekonomi Feminisme Filsafat...

 

2006 NCAA Division I women's basketball tournament

Maryland's first title, beating Duke 78-75 2006 NCAA Division Iwomen's basketball tournament2006 Women's Final Four logoTeams64Finals siteTD GardenBoston, MassachusettsChampionsMaryland Terrapins (1st title, 1st title game,3rd Final Four)Runner-upDuke Blue Devils (2nd title game,4th Final Four)SemifinalistsNorth Carolina Tar Heels (2nd Final Four)LSU Tigers (3rd Final Four)Winning coachBrenda Frese (1st title)MOPLaura Harper (Maryland) NCAA Division I women's tournaments «2005 2007»...

Holozoa

Holozoa TaksonomiSuperdomainBiotaSuperkerajaanEukaryotaKladAmorpheaKladObazoaKladOpisthokontaTanpa nilaiHolozoa Subgrup Ichthyosporea (= Mesomycetozoea) Pluriformea Corallochytrium Syssomonas Filozoa Filasterea Choanozoa Choanoflagellata Metazoa (hewan) lbs Holozoa adalah sekelompok organisme yang termasuk hewan dan beberapa mikroorganisme, tetapi tidak dengan jamur.[1][2][3][4] Holozoa juga merupakan nama lama dari genus Urochordata Distaplia.[5] Karen...

 

Hutama Karya

PT Hutama Karya (Persero)Logo tanpa sloganSebelumnyaPN Hutama Karya (1961 - 1973)JenisPerusahaan perseroan (Persero)IndustriKonstruksiPendahuluHollandsche Beton Maatschappij nv Kantoor IndonesiëDidirikan29 Maret 1961; 63 tahun lalu (1961-03-29)KantorpusatJakarta, IndonesiaWilayah operasiIndonesiaTokohkunciBudi Harto[1](Direktur Utama)Budiman[2](Komisaris Utama)JasaPembangunan gedung dan infrastrukturPengusahaan jalan tol (terutama jaringan Jalan Tol Trans-Sumatra)Pengemb...

 

Синелобый амазон

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

Синелобый амазон

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

 

Горностай

У этого термина существуют и другие значения, см. Горностай (значения). Горностай Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:Челюстнороты...

 

土库曼斯坦总统

土库曼斯坦总统土库曼斯坦国徽土库曼斯坦总统旗現任谢尔达尔·别尔德穆哈梅多夫自2022年3月19日官邸阿什哈巴德总统府（Oguzkhan Presidential Palace）機關所在地阿什哈巴德任命者直接选举任期7年，可连选连任首任萨帕尔穆拉特·尼亚佐夫设立1991年10月27日 土库曼斯坦土库曼斯坦政府与政治 国家政府 土库曼斯坦宪法 国旗 国徽 国歌 立法機關（英语：National Council of Turkmenistan） ...

Feminist language reform

Effort to change how language is used to gender people, activities and ideas The examples and perspective in this article may not represent a worldwide view of the subject. You may improve this article, discuss the issue on the talk page, or create a new article, as appropriate. (June 2018) (Learn how and when to remove this message) Part of a series onFeminism History Feminist history History of feminism Women's history American British Canadian German Waves First Second Third Fourth Timelin...

 

Exodusters

Movement of African Americans in Kansas to live freely from their former slave masters Exoduster movementRefugees on Levee, 1879Date1879LocationUnited StatesAlso known asExodus of 1879CauseDisenfranchisement after the Reconstruction Era Jim Crow economy Mass racial violence in the United States ParticipantsGovernment of the United StatesAfrican AmericansOutcome 98,000 sign emigration papers Around 26,000 African Americans arrive in Kansas Part of a series onAfrican Americans History Periods T...

 

Specialist school

Type of school This article is about schools specialising in certain areas of the curriculum. For other types of school sometimes known by this name, see Specialist school (disambiguation). Nottingham University Academy of Science and Technology is a STEM specialist school in Nottingham, England. Specialist schools, also known as specialised schools or specialized schools, are schools which specialise in a certain area or field of curriculum.[1][2][3] In some countries...

張平江

張平江个人资料出生1902年？月？日四川廣安逝世1975年1月21日成都籍贯四川廣安配偶黃惠平 張平江（1902年—1975年1月21日）。四川省廣安縣人。民國37年（1948年）在全國性職婦團體工人婦女當選第一屆立法委員。 生平[1] 先後就讀岳池縣立女子中學、成都第一女子師範學校、北京女子高等師範學校，並被選為學生自治會主席、北京國立八校聯合會理事 中國國民黨上海市�...

 

Snake Bite Love

1998 studio album by MotörheadSnake Bite LoveStudio album by MotörheadReleased10 March 1998Recorded1998[1]StudioThe Valley[1]GenreHeavy metalLength44:53LabelSPV/SteamhammerProducerHoward Benson & Motörhead[1]Motörhead chronology Protect the Innocent(1997) Snake Bite Love(1998) Everything Louder than Everyone Else(1999) Professional ratingsReview scoresSourceRatingAllMusic[2]Rock Hard8/10[3] Snake Bite Love is the fourteenth studio album...

 

Eduard von Steiger

Swiss politician Eduard von SteigerOfficial portait, 195151st President of the Swiss ConfederationIn office1 January 1951 – 31 December 1951Succeeded byJean-Marie MusyConstituencyCanton of BernMember of the Federal Council (Switzerland)In office1 January 1941 – 31 December 1951 Personal detailsBornAdolf Eduard von Steiger(1881-07-02)2 July 1881Langnau im Emmental, SwitzerlandDied10 February 1962(1962-02-10) (aged 80)Bern, SwitzerlandSpouse Beatrice Gabrielle von Muelinen ​ ...

MAZE☆爆熱時空

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）出典検索?: MAZE☆爆熱時空 – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2024年9月) MAZE☆爆熱時空 ジャンル ロボット[1]、...

 

LibreOffice Writer

Open-source word processor LibreOffice WriterLibreOffice Writer 7.2.4 (released in December 2021, running on Linux and KDE Plasma 5 with the Breeze icon set)Developer(s)The Document FoundationStable releaseFresh:[1] 24.8.2[2]  (27 September 2024)Still:[1] Operating systemLinux, FreeBSD, macOS, Microsoft Windows and via ecosystem partners: Android, iOS, iPadOS, ChromeOS and Online.PredecessorOpenOffice.org WriterTypeWord processorLicenseMPLv2.0 (secondary license G...