Share to: share facebook share twitter share wa share telegram print page

Đa đồ thị

Trong toán học, đa đồ thị (multigraph hay pseudograph) là một đồ thị được phép có nhiều cạnh (còn gọi là cạnh song song), nghĩa là các cạnh có cùng một nút kết thúc. Do đó hai đỉnh có thể được kết nối bởi nhiều cạnh.

Một đa đồ thị với nhiều cạnh (màu đỏ) vài khuyên (màu xanh). Không phải tất cả các tác giả đều cho là đa đồ thị được có khuyên.

Đa đồ thị vô hướng

Ta có một đa đồ thị G:=(V, E) với:

  • V là một tập các đỉnh.
  • E là một đa tập các cặp đỉnh không có thứ tự, cạnh không có hướng.

Đa đồ thị có thể được dùng trong mô hình các chuyến bay bởi các hãng hàng không. Trong trường hợp này đa đồ thị sẽ là một đồ thị có hướng với những cặp cạnh có hướng song song nhau nối các thành phố để cho biết có thể bay từ vị trí này đến vị trí kia.

Một số tác giả cũng cho phép đa đồ thị có khuyên, nghĩa là có một cạnh nối một đỉnh với chính nó, trong khi những người khác gọi là pseudographs và cho rằng đa đồ thị (multigraph) là không có khuyên.

Đa đồ thị có hướng

Một đa đồ thị có hướng (multidigraph) mà độ thị được phép có nhiều cung (arc),cung có cùng một đỉnh đầu và cuối. Một đa đồ thị có hướng G:=(V,A) với

  • V là tập các đỉnh.
  • A là tập các cặp đỉnh có thứ tự, được gọi là cạnh có hướng.

Một đa đồ thị hỗn hợp G:=(V,E, A) cũng có thể được định nghĩa như đồ thị hỗn hợp.

Ngoài ra ta có một đa đồ thị có hướng G:=(V, A, s, t) với

  • V là một tập các đỉnh
  • V là một tập các cạnh
  • , gán cho mỗi cạnh đỉnh nguồn của nó
  • , gán cho mỗi cạnh đỉnh đích của nó

Chú thích


Tham khảo

  • Balakrishnan, V. K.; Graph Theory, McGraw-Hill; 1 edition (ngày 1 tháng 2 năm 1997).
  • Bollobás, Béla; Modern Graph Theory, Springer; 1st edition (ngày 12 tháng 8 năm 2002).
  • Diestel, Reinhard; Graph Theory, Springer; 2nd edition (ngày 18 tháng 2 năm 2000).
  • Gross, Jonathan L, and Yellen, Jay; Graph Theory and Its Applications, CRC Press (ngày 30 tháng 12 năm 1998).
  • Gross, Jonathan L, and Yellen, Jay; (eds); Handbook of Graph Theory. CRC (ngày 29 tháng 12 năm 2003).
  • Harary, Frank; Graph Theory, Addison Wesley Publishing Company (January 1995).
  • Zwillinger, Daniel; CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC; 31st edition (ngày 27 tháng 11 năm 2002).

Read other articles:

Юзеф Клеменс Чорторийський

Юзеф Клеменс Чорторийський Народився 21 листопада 1740(1740-11-21)Помер 15 лютого 1810(1810-02-15)[1] (69 років)Варшава, Варшавське герцогство[1]Поховання Кальварія-Зебжидовська (парк)[1]Країна  Річ ПосполитаДіяльність дипломатЧленство Торговицька конфедераціяПосада учас�...

 

Umbraculum

Papal regalia For the mollusc genus, see Umbraculum (gastropod). Coat of arms during the sede vacante – featuring an umbraculum Umbraculum in the Basilica of St. Louis, King of France The umbraculum (Italian: ombrellone, big umbrella,[1] in basilicas also conopaeum[2]) is a historic piece of the papal regalia and insignia, once used on a daily basis to provide shade for the pope (Galbreath, 27). Also known as the pavilion, in modern usage the umbraculum is a symbol of the Ca...

 

Эстония на летних Олимпийских играх 1936

Эстония на Олимпийских играх Код МОК EST НОК Эстонский олимпийский комитетОфициальный сайт Олимпийские игры в Берлине Спортсмены 33 в 8 видах спорта Знаменосец Эрих Алтосаар МедалиМесто 13 Золото Серебро Бронза Всего 2 2 3 7 Участие в летних Олимпийских играх 1920 1924...

Pesantren

Bagian dari seriPendidikan di Indonesia Kementerian Pendidikan, Kebudayaan, Riset, dan Teknologi Republik Indonesia Pendidikan anak usia dini TK RA KB Pendidikan dasar (kelas 1–6) SD MI Paket A Pendidikan dasar (kelas 7–9) SMP MTs Paket B Pendidikan menengah (kelas 10–12) SMA MA SMK MAK SMA SMTK SMAK Utama Widya Pasraman Paket C Pendidikan tinggi Perguruan tinggi Akademi Akademi komunitas Institut Politeknik Sekolah tinggi Universitas Lain-lain Madrasah Pesantren Sekolah alam Sekolah ru...

 

Shepley, Rutan and Coolidge

American architectural firm Shepley, Rutan and Coolidge was a successful architecture firm based in Boston, Massachusetts, United States, operating between 1886 and 1915, with extensive commissions in monumental civic, religious, and collegiate architecture in the spirit and style of Henry Hobson Richardson. History This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (January 2021) ...

 

قالب:سياسة الولايات المتحدة

جزء من سلسلة مقالات سياسة الولايات المتحدةالولايات المتحدة الدستور الدستور الضرائب السلطة التنفيذية الحكومة الفيدرالية الرئيس (قائمة) جو بايدن نائب الرئيس (قائمة) كامالا هاريس المكتب التنفيذي للرئيس الوكالات الفيدرالية السلطة التشريعية الكونغرس مجلس النواب الناطق باسم...

Fire Museum of Greater Cincinnati

United States historic placeCourt Street FirehouseU.S. National Register of Historic PlacesCincinnati Local Historic Landmark Main facadeShow map of OhioShow map of the United StatesLocation311 W. Court St., Cincinnati, OhioCoordinates39°6′19″N 84°31′10″W / 39.10528°N 84.51944°W / 39.10528; -84.51944Arealess than one acreBuilt1906Architectural styleRenaissanceNRHP reference No.74001510[1]Added to NRHPJuly 18, 1974 The Fire Museum of G...

 

Sarit Thanarat

Marsekal lapanganSarit Thanaratสฤษดิ์ ธนะรัชต์Perdana Menteri Thailandke-11Masa jabatan20 Oktober 1958 – 8 Desember 1963Penguasa monarkiBhumibol AdulyadejPendahuluThanom KittikachornPenggantiThanom Kittikachorn Informasi pribadiLahir(1908-06-16)16 Juni 1908Bangkok, SiamMeninggal8 Desember 1963(1963-12-08) (umur 55)Bangkok, ThailandKebangsaanThaiSuami/istriNuanchan Thanarat (dua anak), Chawee (dua anak), Praima (dua anak), Vichitra Thanarat (tidak me...

 

Sōja, Okayama

Sōja 総社市Kota BenderaLambangLokasi Sōja di Prefektur OkayamaNegara JepangWilayahChūgokuPrefektur OkayamaPemerintahan • Wali kotaSōichi KataokaLuas • Total212 km2 (82 sq mi)Populasi (Oktober 1, 2015) • Total66.855 • Kepadatan315,4/km2 (8,170/sq mi)Zona waktuUTC+9 (JST)Kode pos719-1192Simbol • PohonAcer• BungaAstragalus sinicus• BurungGrus japonensisNomor telepon0866-92-8200Alamat1-1-1 Chū

Birth Crisis

Birth CrisisAlbum studio karya Jumbo JetDirilis2002Direkam10 Oktober - 7 November 2001GenreHardcoreLabelNo Label RecordsProduserNo Label Records/Hangar Management Birth Crisis adalah album ke dua dari band beraliran hardcore punk/ thrash metal asal Jakarta yaitu Jumbo Jet. Tinjauan Covernya menggambarkan dua cerobong asap pabrik dengan matahari di tengah atas cerobong, yang menggambarkan kekeringan dunia dan judul albumnya pun diambil dari keadaan ekonomi dunia yang pada saat itu sedang d...

 

The Silent Service

Halaman ini berisi artikel tentang serial manga Jepang. Untuk kegunaan lain, lihat Silent Service. The Silent ServiceSampul volume pertama沈黙の艦隊(Chinmoku no Kantai)GenreDrama, Militer MangaPengarangKaiji KawaguchiPenerbitKodanshaMajalahWeekly MorningDemografiSeinenTerbit1988 – 1996Volume32 Video animasi orisinalSutradaraRyōsuke TakahashiStudioSunriseTayang 3 Maret 1996 – 25 Januari 1998Episode3  Portal anime dan manga The Silent Service (Jepang: 沈黙の艦隊code: ja ...

 

Partai politik

Anggota partai-partai politik bersama-sama berkoordinasi untuk mencapai dan mempergunakan kekuasaan politik. Bagian dari seri PolitikPartai politik Spektrum politik Sayap kiri Kiri jauhKiri tengah Sentris Kiri tengahTengah radikalKanan tengah Sayap kanan Kanan tengahKanan jauh Platform/Ideologi Anarkis Demokrasi Kristen Komunis Konservatif Demokrasi Environmentalis Fasis Fundamentalis Globalis Hijau Internasionalis Liberal Libertarian Nasionalis Partai Pembajakan Populis Progresif Regionalis ...

The Curious City

The topic of this article may not meet Wikipedia's notability guideline for music. 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 be shown, the article is likely to be merged, redirected, or deleted.Find sources: The Curious City – news · newspapers · books · scholar · JSTOR (February ...

 

Kuda nil

Kuda nil Status konservasi Rentan (IUCN 3.1)[1] Klasifikasi ilmiah Kerajaan: Animalia Filum: Chordata Kelas: Mammalia Ordo: Artiodactyla Famili: Hippopotamidae Genus: Hippopotamus Spesies: H. amphibius Nama binomial Hippopotamus amphibiusLinnaeus, 1758 Distribusi kuda nil Kuda nil[2] atau badak air[3] (Hippopotamus amphibius) adalah mamalia dari keluarga Hippopotamidae yang berukuran besar, omnivora, dan berasal dari Afrika sub-Sahara. Kuda nil adalah hewan d...

 

Hwata dynasty

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) This article may need to be rewritten to comply with Wikipedia's quality standards. You can help. The talk page may contain suggestions. (October 2011) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (Novembe...

National Security Council (Turkey)

Turkish government agency in charge of national security and foreign policy Not to be confused with National Security Council (Turkey, 1980). National Security CouncilMilli Güvenlik KuruluAgency overviewFormedDecember 11, 1962 (1962-12-11)Preceding agenciesYüksek Müdafaa Meclisi (1933–1949)Milli Savunma Yüksek Kurulu (1949–1962)JurisdictionPresident Recep Tayyip Erdoğan (chairman)HeadquartersPresidential ComplexAnnual budget₺ 34.8 million (2019)[1]Agency exec...

 

Confessions (2010 film)

2010 film ConfessionsFilm posterDirected byTetsuya NakashimaWritten byTetsuya NakashimaBased onKokuhakuby Kanae MinatoProduced byMinami IchikawaStarringTakako MatsuEdited byYoshiyuki KoikeDistributed byToho CompanyRelease date 5 June 2010 (2010-06-05) Running time106 minutesCountryJapanLanguageJapaneseBox office$45.2 million[1] Confessions (告白, Kokuhaku) is a 2010 Japanese psychological thriller film directed by Tetsuya Nakashima, based on author Kanae Minato's 2008...

 

Saint Francis Receiving the Stigmata (Rubens)

Saint Francis Receiving the Stigmata by Rubens Saint Francis Receiving the Stigmata is an oil painting on canvas by Peter Paul Rubens, produced for the Franciscan monastic church in Ghent, probably part of a commission for three works for the same church – the others were St Mary Magdalene in Ecstasy (Palace of Fine Arts, Lille) and The Virgin Mary and Saint Francis Saving the World from Christ's Anger (Royal Museum of Fine Arts, Brussels). It measures 265.5 cm (104.5 in) x 193 cm (75.9 in)...

Guan Xueting

Chinese ice dancer Guan XuetingFull nameGuan XuetingBorn (1992-12-04) December 4, 1992 (age 31)Shenyang, LiaoningHeight1.58 m (5 ft 2 in)Figure skating careerCountry ChinaPartnerWang MengCoachGao GeSkating clubShenyang FSC In this Chinese name, the family name is Guan. Guan Xueting (simplified Chinese: 关雪婷; traditional Chinese: 關雪婷; pinyin: Guān Xuětíng; born December 4, 1992, in Shenyang, Liaoning) is a Chinese ice dancer. With partner Wang...

 

Phenazine

Phenazine Names Preferred IUPAC name Phenazine[1] Other names Dibenzopyrazine9,10-DiazaanthraceneAzophenyleneacridizine Identifiers CAS Number 92-82-0 Y 3D model (JSmol) Interactive image ChEBI CHEBI:36674 Y ChEMBL ChEMBL119870 Y ChemSpider 4593 Y ECHA InfoCard 100.001.995 PubChem CID 4757 UNII 2JHR6K463W Y CompTox Dashboard (EPA) DTXSID2059069 InChI InChI=1S/C12H8N2/c1-2-6-10-9(5-1)13-11-7-3-4-8-12(11)14-10/h1-8H YKey: PCNDJXKNXGMECE-UHFFFAOYSA-N...

 
Kembali kehalaman sebelumnya