Grafteori

Den komplette grafen K5 er ein graf med fem nodar som alle er knytte opp til kvarandre med kantar.

Grafteori er den greina av matematikk der ein studerer eigenskapane til grafar. Ein graf består av ei mengd hjørne eller nodar, og ei mengd kantar, der kvar kant bind saman to hjørne. På figuren er eit døme på ein graf med fem nodar og ti kantar.

Formelt er det vanleg å definera ein graf som eit par , der er ei ikkje-tom mengd med nodar, og er ei mengd med undermengder av der kvar undermengd har to element. Strengt tatt er grafen desse mengdene av hjørne og kantar – ikkje teikninga av dei.

Grafteori vart grunnlagd av Leonhard Euler då han publiserte ein artikkel om problemet «Bruene i Königsberg» i 1736.

Grafteoretiske omgrep

To hjørne er naboar viss dei er forbunde med ein kant. Ein kant er insident til hjørna som han bind saman.

Ein graf er enkel viss det aldri er meir enn éin kant mellom to naboar, og ingen hjørne er nabo med seg sjølv. Ein slik kant blir kalla ei løkke. Ein graf som inneheld løkker, eller som inneheld naboar som er forbunde med meir enn éin kant, blir kalla ein multigraf.

En veg i ein graf er ei mengd kantar i rekkefølgje, slik at to kantar etter kvarandre alltid har eit hjørne felles. Ein sti er ein veg der kvart hjørne opptrer høgst éin gong. Ein sykel er ein veg der det første og det siste hjørnet er det same, mens alle andre hjørne opptrer høgst éin gong.

Ein planar graf er ein graf som kan teiknast i eit plan eller på ei kuleflate slik at ingen kantar kryssar kvarandre. Ein graf er samanhengande viss kvart par av ulike hjørne er knytte saman med ein sti.

To grafar er isomorfe viss det finst ei avbilding frå hjørna i den eine grafen til hjørna i den andre grafen, slik at to hjørne er naboar i den første grafen viss og berre viss dei korresponderande hjørna er naboar i den andre grafen.

Bakgrunnsstoff

Wikimedia Commons har multimedia som gjeld: Grafteori

Read other articles:

Pantai Nganteb

Pantai Nganteb adalah sebuah pantai di pesisir selatan yang secara administratif berada di Dusun Sukorejo, Desa Tumpakrejo, Kecamatan Gedangan, Kabupaten Malang, Jawa Timur atau sekitar 72 km dari Kota Malang. Untuk mengunjungi Pantai Nganteb, Anda bisa mengikuti jalan menuju Pantai Balekambang, karena lokasinya sekitar 3,5 km ke arah timur sebelum masuk Pantai Balekambang. Pantai Nganteb ini terletak setelah Pantai Wonogoro jika dari arah Balekambang. Pantai Wonogoro berhimpitan de...

 

The Ward (film)

2010 American filmThe WardFilm posterDirected byJohn CarpenterWritten byMichael RasmussenShawn RasmussenProduced by Doug Mankoff Peter Block Mike Marcus Andrew Spaulding Starring Amber Heard Mamie Gummer Danielle Panabaker Laura-Leigh Lyndsy Fonseca Mika Boorem Jared Harris CinematographyYaron OrbachEdited byPatrick McMahonMusic byMark KilianThe NewbeatsProductioncompanies Echo Lake Entertainment[1] A Bigger Boat[1] Distributed by ARC Entertainment[2] XLrator Media ...

 

العلاقات الأرجنتينية الغانية

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

Laura Marx

Jenny Laura MarxLaura Marx pada 1860Lahir(1845-09-26)26 September 1845Brussels, BelgiaMeninggal25 November 1911(1911-11-25) (umur 66)Draveil, PrancisSebab meninggalBunuh diriMakamPemakaman Père LachaiseSuami/istriPaul LafargueOrang tuaKarl Marx Jenny von Westphalen Jenny Laura Marx (26 September 1845 – 25 November 1911), yang lebih dikenal sebagai Laura Marx, adalah putri kedua dari pasangan Karl Marx dan Jenny von Westphalen. Pada 1868, ia menikahi Paul Lafargue. ...

 

Arnhem (kapal)

Sejarah Republik Belanda Nama ArnhemPemilik Vereenigde Oostindische CompagniePembangun Vereenigde Oostindische Compagnie, AmsterdamNasib Kandas di Saint Brandon Rocks (lepas pantai Mauritius) pada 12 Februari 1662 Ciri-ciri umum Kelas dan jenis East Indiaman BelandaTonase muatan 1.000 tonPendorong LayarTata layar Tiga menara Arnhem atau Aernem[1] adalah kapal layar kelas East Indiaman milik Belanda yang muncul di beberapa peristiwa sejarah terkenal. Nama kapal ini diambil dari nama k...

 

Fabulous Boys

Artikel ini sudah memiliki daftar referensi, bacaan terkait, atau pranala luar, tetapi sumbernya belum jelas karena belum menyertakan kutipan pada kalimat. Mohon tingkatkan kualitas artikel ini dengan memasukkan rujukan yang lebih mendetail bila perlu. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Fabulous BoysDari kiri ke kanan. Hwang In Deok, Lyan Cheng, Jiro Wang dan Evan YoGenreRomansa KomediPemeranLyan ChengJiro WangHwang In DeokEvan YoLagu pembukaPromise (約定) o...

Pemilihan umum Presiden Polandia 2010

Pemilihan Umum Presiden Polandia 20102005201520 Juni dan 4 Juli 2010Kandidat   Calon Bronisław Komorowski Jarosław Kaczyński Partai Civic Platform Hukum dan Keadilan PresidenBronisław Komorowski (penjabat) Civic Platform Pemilihan Umum Presiden Polandia dilaksanakan pada 20 Juni 2010 di Polandia. Karena tidak ada kandidat yang mendapat suara mayoritas, maka pemilihan putaran kedua dilaksanakan pada 4 Juli 2010.[1] Pemilihan putaran kedua dimenangkan oleh Penjabat Presiden Po...

 

Indira P. P. Bora

GuruIndira P. P. BoraLahir1949Golaghat, Assam, IndiaKebangsaanIndianWarga negaraIndiaPendidikanpascasarjanaPekerjaanSatriya PenariDikenal atasSatriya, Bharatnatyam, KuchipudiGelarGuruAnakSatuPenghargaanPadma Shri (2020), Sangeet Natak Akademi Award (1996)Situs webhttp://kalabhumiindia.com Indira P. P. Bora adalah seorang pedansa Satriya dari Assam, India.[1][2] Dilatih di Bharatnatyam selama 13 tahun di bawah Guru Rukmini Devi Arundale dan di Kuchipudi di bawah bimbingan Guru...

 

Andronikus

AndronikusAndronicus, Athanasius dari Christianoupolis dan YuniasDihormati diGereja Ortodoks TimurGereja Ortodoks OrientalPersekutuan AnglikanGereja KatolikPesta17 Mei, 22 PashonsAtributKemartiran Kristen Andronikus dari Pannonia (Yunani: Ἀνδρόνικος) adalah seorang pengikut Kristen abad ke-1 yang disebutkan oleh Rasul Paulus: Salam kepada Andronikus dan Yunias, saudara-saudaraku sebangsa, yang pernah dipenjarakan bersama-sama dengan aku, yaitu orang-orang yang terpandang di ant...

CHAS-FM

Radio station in Sault Ste. Marie, Ontario CHAS-FMSault Ste. Marie, OntarioCanadaBroadcast areaAlgoma DistrictChippewa County, MichiganFrequency100.5 MHzBrandingKiSS 100.5ProgrammingFormatHot adult contemporaryOwnershipOwnerRogers Radio(Rogers Media, Inc.)Sister stationsCJQM-FM, CIRS (defunct)HistoryFirst air dateMay 15, 1964Former call signsCJIC-FM (1964–1977)Technical informationClassCERP13,900 wattsHAAT125 meters (410 ft)LinksWebcastListen LiveWebsitekisssoo.com CHAS-FM (100.5 MHz) ...

 

Sari (Iran)

Pour les articles homonymes, voir Sari. Sari (fa) سارى Administration Pays Iran Province Mazandéran Indicatif téléphonique international +(98) Démographie Population 262 627 hab. (2005) Densité 5 161 hab./km2 Géographie Coordonnées 36° 33′ nord, 53° 06′ est Altitude 50 m Superficie 5 089 ha = 50,89 km2 Localisation Géolocalisation sur la carte : Iran Sari Géolocalisation sur la carte : Iran Sar...

 

Lavausseau

LavausseaucomuneLavausseau – Veduta LocalizzazioneStato Francia Regione Nuova Aquitania Dipartimento Vienne ArrondissementPoitiers CantoneVouneuil-sous-Biard TerritorioCoordinate46°33′N 0°05′E / 46.55°N 0.083333°E46.55; 0.083333 (Lavausseau)Coordinate: 46°33′N 0°05′E / 46.55°N 0.083333°E46.55; 0.083333 (Lavausseau) Superficie24,66 km² Abitanti812[1] (2009) Densità32,93 ab./km² Altre informazioniCod. postale864...

Ciudad Perdida

Rediscovered lost city in Colombia Ciudad PerdidaView of the central area of the city. Wooden structures once stood on the stone platforms.Shown within ColombiaAlternative nameTeyuna, Buritaca-200LocationMagdalena Department, ColombiaRegionSierra Nevada de Santa MartaCoordinates11°2′16.79″N 73°55′30.69″W / 11.0379972°N 73.9251917°W / 11.0379972; -73.9251917TypeSettlement Ciudad Perdida (Spanish for lost city; also known as Teyuna and Buritaca-200[1...

 

Arab Agricultural Revolution

Arab transformation of agriculture in Medieval Spain The Arabs transformed agriculture during the Islamic Golden Age by spreading major crops and techniques such as irrigation across the Old World. The Arab Agricultural Revolution was the transformation in agriculture in the Old World during the Islamic Golden Age (8th to 13th centuries). The agronomic literature of the time, with major books by Ibn Bassal and Abū l-Khayr al-Ishbīlī, demonstrates the extensive diffusion of useful plants to...

 

Appello Cristiano Democratico

Appello Cristiano Democratico(NL) Christen-Democratisch Appèl LeaderHenri Bontenbal PresidenteHans Huibers Stato Paesi Bassi SedeBuitenom 18 Postbus, 30453 L'Aia AbbreviazioneCDA Fondazione11 ottobre 1980 Derivato da Partito Popolare Cattolico Unione Cristiana-Storica Partito Anti-Rivoluzionario IdeologiaCristianesimo democraticoConservatorismo sociale CollocazioneCentro[1][2][3] / Centro-destra[4][5][6][7] Partito europe...

1st Armoured Infantry Brigade (United Kingdom)

Inactive British Army formation 1st (Guards) Brigade redirects here. For a similarly designated formation, see 1st Guards Brigade (United Kingdom). 1st (Guards) Brigade1st Brigade1st Infantry Brigade (Guards)1st Infantry Brigade1st Mechanized Brigade1st Armoured Infantry BrigadeInsignia of the 1st Armoured Infantry Brigade.Active1899–2022Country United KingdomBranch British ArmyTypeArmoured Infantry, Mechanized Infantry, Light InfantrySizeBrigadePart of3rd (United Kingdom) Di...

 

مايكروسوفت أوفيس 2016

مايكروسوفت أوفيس 2016الشعارمعلومات عامةنوع برنامج إنتاجيةنظام التشغيل ويندوز 7 وما يليه ويندوز سيرفر 2008 أر 2 وما يليه[1]المنصة أي إيه-32، إكس86-64النموذج المصدري حقوق التأليف والنشر محفوظة متوفر بلغات بالكامل (40): الإنجليزية، العربية، البلغارية، الصينية المبسطة، الصينية ا�...

 

Yuri Trutnev (scientist)

Soviet physicist (1927–2021) For Russan politician, see Yury Trutnev. Yuri TrutnevЮрий ТрутневTrutnev in 2013Born(1927-11-02)2 November 1927Moscow, Russian Soviet Federative Socialist RepublicDied6 August 2021(2021-08-06) (aged 93)Sarov, RussiaNationalityRussianCitizenship RussiaAlma materLeningrad State UniversityKnown forSoviet atomic bomb projectAwardsSee honorsScientific careerFieldsPhysicsInstitutions VNIIEF National Research Nuclear University MEPhI Yuri...

Dichapetalaceae

Family of flowering plants Dichapetalaceae Gifblaar or ratbane (Dichapetalum cymosum) Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Angiosperms Clade: Eudicots Clade: Rosids Order: Malpighiales Family: DichapetalaceaeBaill.[1] Genera Dichapetalum Stephanopodium Tapura Dichapetalaceae is a family of flowering plants, consisting of 3 genera and about 170 species.[2][3] Members of this family are trees, shrubs or lianas found in tropical and subtr...

 

Langston Hughes

American writer and social activist (1901–1967) For other uses, see Langston Hughes (disambiguation). Langston HughesPortrait by Carl Van Vechten, 1936BornJames Mercer Langston Hughes(1901-02-01)February 1, 1901Joplin, Missouri, U.S.DiedMay 22, 1967(1967-05-22) (aged 66)New York City, U.S.OccupationPoetcolumnistdramatistessayistnovelistEducationColumbia UniversityLincoln University (BA)Period1926–1964RelativesCharles Henry Langston (grandfather)John Mercer Langston (uncle)Mary Sampso...