Teorija grafova

Crtanje grafa

U matematici i računarstvu teorija grafova jest proučavanje grafova, koji su matematičke strukture korištene za modeliranje parova odnosa između objekata. Graf u ovom kontektstu napravljen je od tjemena, čvorova, ili tačaka koje se spajaju ivicama, lukovima ili linijama. Može biti neusmjeren, što znači da nema razlike između dva tjemena povezana s ivicom, ili njeni vrhovi mogu biti usmjereni sa jednog tjemena na drugo. Grafovi su jedan od primarnih predmeta studija u diskretnoj matematici.

Definicije

Definicije u teoriji grafova variraju. Ovdje su navedeni samo neki od osnovnih načina definiranja grafova i povezanih matematičkih struktura.

Graf

U općenitom smislu pojma,[1][2] graf je poredani par G = (V, E) koji se sastoji od skupa V tjemena ili čvorova ili tačaka zajedno sa skupom E ivica ili lukova ili linija, koji su dvoelementni podskupovi od V (npr., ivica je povezana sa dva tjemena, a relacija je predstavljena kao neporedani par tjemena s obzirom na određene ivice). Da bi se izbjegla dvosmislenost, ova vrsta grafa može se opisati upravo kao neusmjeren i jednostavan.

Drugi smisao grafa proistječe iz različitih koncepcija ivice skupa. U općenitijem smislu,[3] V je skup zajedno s relacijama događaja koji su povezani sa svakom ivicom dva tjemena. U drugom uopćenom smislu E je multiskup neporedanih parova (ne nužno različitih) tjemena. Većina autora taj tip objekta naziva multigraf ili pseudograf.

Tjemena koja pripadaju ivici zovu se krajevi ili krajevi čvorova ruba. W tjeme može postojati u grafu i ne pripadati ivici.

V i E često se uzimaju kao ograničeni i većina dobro poznatih rezultata nije istinita (ili su različiti) za neograničene grafove jer većina argumenata potpada pod ograničen slučaj. Red grafa je |V|, njegov broj tjemena. Veličina grafa je |E|, njegov broj ivica. Stepen ili valencija tjemena je broj ivica koje se na to spajaju, gdje se ivica koja spaja tjeme sa sobom (petlja) broji dvaput.

Za ivicu {x, y} teoretičari grafova često koriste nešto skraćenu notaciju xy.

Reference

  1. ^ Iyanaga and Kawada, 69 J, str. 234
  2. ^ Biggs, str. 4.
  3. ^ Graham et al., p. 5.

Vanjski linkovi

Commons logo
Commons logo
Commons ima datoteke na temu: Teorija grafova
  • Teorija grafova (autor Reinhard Diestel) (en)
  • Teorija grafova s primjerima (en)
  • Hazewinkel, Michiel, ured. (2001), "Graph theory", Matematička enciklopedija, Kluwer Academic Publishers, ISBN 978-1556080104
  • Teorija grafova Arhivirano 16. 1. 2012. na Wayback Machine (lekcije) (en)

Read other articles:

Let Me See the Booty

2008 single by The-Dream featuring Lil JonLet Me See the BootySingle by The-Dream featuring Lil Jonfrom the album Love vs. Money ReleasedNovember 25, 2008Recorded2008GenreR&BcrunkLength3:25LabelRadio Killa/Def JamSongwriter(s)T. Nash, J. SmithProducer(s)The-Dream and Lil JonThe-Dream singles chronology All I Need (2008) Let Me See the Booty (2008) Rockin' That Shit (2008) Lil Jon singles chronology Krazy(2008) Let Me See the Booty(2008) Patron Tequila(2009) Let Me See the Booty is...

 

Intubation

Insertion of a tube into the body for medical purposes This term often refers specifically to Tracheal intubation. Not to be confused with Incubation. IntubationICD-9-CM96.0MeSHD007440[edit on Wikidata] Intubation (sometimes entubation) is a medical procedure involving the insertion of a tube into the body. Patients are generally anesthetized beforehand. Examples include tracheal intubation, and the balloon tamponade with a Sengstaken–Blakemore tube (a tube into the gastrointestinal tra...

 

أيلاند بارك (نيويورك)

أيلاند بارك    شعار   الإحداثيات 40°36′11″N 73°39′25″W / 40.603055555556°N 73.656944444444°W / 40.603055555556; -73.656944444444   [1] تقسيم إداري  البلد الولايات المتحدة[2]  التقسيم الأعلى مقاطعة ناسو  خصائص جغرافية  المساحة 1.150377 كيلومتر مربع1.152586 كيلومتر مربع (1 أبريل 201...

Xiumin

Untuk aktor dengan nama yang sama, lihat Kim Min-seok (aktor). Ini adalah nama Korea; marganya adalah Kim. XiuminXiumin pada Februari 2018Nama asal김민석LahirKim Min-seok26 Maret 1990Seongbuk-dong, Seoul, Korea SelatanPekerjaanPenyanyiaktorKarier musikGenreK-popR&BInstrumenVokalTahun aktif2012–sekarangLabelSMArtis terkaitEXOEXO-MEXO-CBXSM TownNama KoreaHangul김민석 Hanja金珉錫 Alih AksaraGim Min-seokMcCune–ReischauerKim MinsŏkNama panggungHangul시우민 Hanja秀珉 Ali...

 

Groypers

Loose group of white nationalist activists, provocateurs, and internet trolls For the cartoon after which the group is named, see Pepe the Frog § Groyper. Groypers Groyper meme, the namesake of the groupKey figures Nick Fuentes Michelle Malkin Baked Alaska Jaden McNeil Ideology American nationalism[1] Antisemitism[1] Anti-Zionism[1] Christian right[1] Paleoconservatism[2] White nationalism[1] Political positionFar-rightAffiliations Am...

 

José Leandro Andrade

José Leandro Andrade José Leandro Andrade nel 1926 circa Nazionalità  Uruguay Altezza 180 cm Peso 79 kg Calcio Ruolo Centrocampista Termine carriera 1935 Carriera Squadre di club1 1921-1923 Bella Vista71 (17)1924-1930 Nacional180 (69)1931 Peñarol24 (6)1932-1933 River Plate (M)50 (11)1934 Atlanta18 (0)1935 Talleres (RdE)8 (3)1935 Peñarol10 (4) Nazionale 1923-1930 Uruguay34 (1) Palmarès  Olimpiadi Oro Parigi 1924 Oro Amsterdam 1928  Mondi...

Египтопитек

† Египтопитек Реконструкция внешнего вида египтопитека Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:Четвероно...

 

Reynolds (surname)

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: Reynolds surname – news · newspapers · books · scholar · JSTOR (November 2010) (Learn how and when to remove this message) ReynoldsOriginMeaningson of ReynoldRegion of originLiatroim, England, IrelandFrequency Comparisons:[1] Reynolds is a surname...

 

ソー (オー＝ド＝セーヌ県)

Sceaux 行政国 フランス地域圏 (Région) イル＝ド＝フランス地域圏県 (département) オー＝ド＝セーヌ県郡 (arrondissement) アントニー郡小郡 (canton) 小郡庁所在地INSEEコード 92071郵便番号 92330市長（任期） フィリップ・ローラン（2008年-2014年）自治体間連合 (fr) メトロポール・デュ・グラン・パリ人口動態人口 19,679人（2007年）人口密度 5466人/km2住民の呼称 Scéens地理座標 北緯48度4...

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。 数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券（「壱」が大字） 弐千円日本銀行券（「弐」が大字） 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

 

C&C Yachts

Sailboat manufacturer C&C YachtsCompany typePublicly owned holding company, later a privately held company[1]IndustryBoat buildingPredecessorCuthbertson & Cassian Design, Hinterhoeller Ltd., Belleville Marine Yard Ltd., Bruckmann Manufacturing Ltd.[1]Founded1969[2]FounderErich Bruckmann, George Cassian, George Cuthbertson, George Hinterhoeller, Ian MorchDefunct2017HeadquartersCanada and United StatesKey peopleRobert W. Ball, Erich Bruckmann, George Cassian, Ge...

 

2016年美國總統選舉

2016年美國總統選舉 ← 2012 2016年11月8日 2020 → 538個選舉人團席位獲勝需270票民意調查投票率55.7%[1][2] ▲ 0.8 %   获提名人 唐納·川普 希拉莉·克林頓 政党 共和黨 民主党 家鄉州 紐約州 紐約州 竞选搭档 迈克·彭斯 蒂姆·凱恩 选举人票 304[3][4][註 1] 227[5] 胜出州/省 30 + 緬-2 20 + DC 民選得票 62,984,828[6] 65,853,514[6]...

Beef bourguignon

French beef dish Beef bourguignonA dish of bœuf bourguignonAlternative namesBeef Burgundy, bœuf à la bourguignonneTypeStewPlace of originFranceRegion or stateBurgundyMain ingredientsBeef, red wine (often red Burgundy), beef stock, lardons, onions, bouquet garni, pearl onions, mushrooms Cookbook: Beef bourguignon  Media: Beef bourguignon Beef bourguignon Beef bourguignon (US: /ˌbʊərɡiːnˈjɒ̃/) or bœuf bourguignon (UK: /ˌbɜːf ˈbɔːrɡɪn.jɒ̃/;[1] French: [...

 

العلاقات البوتسوانية الوسط إفريقية

العلاقات البوتسوانية الوسط أفريقية بوتسوانا جمهورية أفريقيا الوسطى   بوتسوانا   جمهورية أفريقيا الوسطى تعديل مصدري - تعديل   العلاقات البوتسوانية الوسط أفريقية هي العلاقات الثنائية التي تجمع بين بوتسوانا وجمهورية أفريقيا الوسطى.[1][2][3][4][5&#...

 

Unione Sportiva Darfo Boario

Questa voce o sezione sull'argomento società calcistiche italiane non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. US Darfo Boario SSDCalcio Neroverdi, Camuni Segni distintiviUniformi di gara Casa Trasferta Colori sociali Nero, verde SimboliCastello InnoForza DarfoAntonio Pedersoli Dati societariCittàDarfo Boario Terme Nazione Italia Confederazione...

Pheasant Island

Uninhabited island between France and Spain For the island in Germany, see Pheasant Island (Eutin). Pheasant IslandÎle des Faisans (French)Isla de los Faisanes (Spanish)Konpantzia (Basque)Pheasant Island (center) from the International Bridge over the Bidasoa river. On the left Irun, Spain; on the right Hendaye, FranceGeographyLocationBidasoaArea0.00682[1] km2 (0.00263 sq mi)Highest elevation6 m (20 ft)AdministrationCurrent: SpainAutonomous communityBasq...

 

Fumetto

Disambiguazione – Se stai cercando altri significati, vedi Fumetto (disambigua). Questa voce o sezione sull'argomento Fumetti è 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ù precisamente. Segui i sugge...

 

Polonsky conspiracy

Polonsky conspiracyPart of the Bolshevik–Makhnovist conflictTypeConspiracyLocationKaterynoslav, UkrainePlannedOctober–November 1919Planned byCommunist Party of UkraineCommanded byYevgeny PolonskyTargetNestor Makhno and other insurgent commandersDate4–5 December 1919 (1919-12-04 – 1919-12-05)Executed byPro-Bolshevik units within the Revolutionary Insurgent Army of UkraineOutcomeFailureCasualties5 conspirators executed vteSouthern Frontof the Russian C...

South African Standard Time

Time zone SAST redirects here. For source code review, see Static application security testing. For the Chinese space agency, see Shanghai Academy of Spaceflight Technology. Time zones of Africa: Light Blue Cape Verde Time[a] (UTC−1) Blue Greenwich Mean Time (UTC) Red Central European TimeWest Africa Time (UTC+1) Ochre Central Africa TimeEastern European TimeEgypt Standard TimeSouth African Standard Time (UTC+2) Green East Africa Time (UTC+3) Turquoise Mauritius Time[b]Seychelles Time[b] (U...

 

User talk:Nick Number

Archives Archive 1Archive 2Archive 3Archive 4Archive 5Archive 6Archive 7Archive 8Archive 9Archive 10 Internet Archive Scholar vs. JSTOR Hello, I see on your user page that you use JSTOR and I'd like to know more about your experience. By my calculations, a good 70 % of the main JSTOR content is now available for everyone at Internet Archive Scholar, with full text search provided e.g. at https://scholar.archive.org/ . The service is still in beta, but I've used it for some source-finding an...