Vizinhança (teoria dos grafos)

Um grafo consistindo de 6 vértices e 7 arestas

Em teoria dos grafos, um vértice adjacente de um vértice v em um Grafo é um vértice que está ligado a v por uma aresta.[1][2] A vizinhança ou adjacência de um vértice v em um grafo G é um subgrafo induzido de G constituído por todos os vértices adjacentes a v e todas as arestas ligando esses dois vértices. Por exemplo, a imagem mostra um gráfico de 6 vértices e 7 arestas. O vértice 5 é adjacente aos vértices 1, 2 e 4, mas não é adjacente aos vértices 3 e 6. A vizinhança do vértice 5 é o grafo com três vértices, 1, 2 e 4, e uma aresta conectando os vértices 1 e 2.

A vizinhança é frequentemente denotada NG(v) ou (quando o grafo não é ambíguo) N(v). A mesma notação de vizinhança também pode ser usada para se referir a um conjunto de vértices adjacentes ao invés dos subgrafos induzidos correspondentes. A adjacência descrita acima não inclui v em si, e mais especificamente, a vizinhança aberta de v; também é possível definir uma adjacência na qual v está incluído, chamada de vizinhança fechada e denotada por NG[v]. Quando não se afirma nada, a vizinhança é considerada aberta.

Vizinhanças podem ser usadas para representar grafos em algoritmos de computador, através da representações de lista de adjacência e matriz de adjacência . Vizinhanças também são usadas no coeficiente de agrupamento de um grafo, que é uma medida da densidade média de suas adjacências. Além disso, muitas classes importantes de grafos podem ser definidas pelas propriedades de suas vizinhanças, ou por simetrias que relacionam vizinhanças umas com as outras.

Um vértice isolado não tem vértices adjacentes. O grau de um vértice é igual ao número de vértices adjacentes. Um caso especial é um laço que une um vértice a ele próprio; se tal aresta existe, o vértice pertence à sua própria vizinhança.

Propriedades locais em grafos

No grafo octaédrico, a vizinhança de qualquer vértice é um 4-ciclo.

Se todos os vértices em G tem adjacências que são isomorfas para o mesmo grafo H,G é dito ser localmente H, e se todos vértices em G tem adjacências que pertencem a alguma família de grafosF, G é dito ser localmente F(Hell 1978, Sedlacek, 1983). Por exemplo, no grafo octaédrico mostrado na figura, cada vértice tem uma adjacência isomorfa a um grafo cíclico de quatro vértices, de modo que o octaedro é localmente C4.

Por exemplo:

  • Qualquer grafo completo Kn é localmente Kn-1. Os únicos grafos que são localmente completos são uniões disjuntas de grafos completos.
  • Um grafo de Turán T(rs,r) é localmente T((r-1)s,r-1). Mais genericamente qualquer grafo Turan é localmente Turan.
  • Todo grafo planar é localmente periplanar. No entanto, nem todos os grafos localmente periplanares são planares.
  • Todo grafo k-cromático é localmente (k-1)-cromático. Todo grafo localmente k-cromático tem um número cromático .[3]
  • Se uma família de grafos F é fechada sob a operação de tomar subgrafos induzidos, então cada grafo em F é também localmente F. Por exemplo, todos os grafos cordais são localmente cordais; cada grafo perfeito é localmente perfeito; todos os grafos de comparabilidade são localmente comparáveis.
  • Um grafo é localmente cíclico se cada vizinhança é um ciclo. Por exemplo, o octaedro é o único grafo localmente C4, o icosaedro é o único grafo localmente C5 e o gráfico Paley de ordem 13 é localmente C6.

Referências

  1. ↑ Even, Shimon (1979). Graph Algorithms. Rockville, Maryland: Computer Science Press. 249 páginas. ISBN 0-914894-21-8 
  2. ↑ Szwarcfiter, Jayme Luiz (1988). Grafos e algoritmos computacionais. Rio de Janeiro: Campus. ISBN 85-7001-341-8 
  3. ↑ Wigderson, Avi (1983). «Improving the performance guarantee for approximate graph coloring». Journal of the ACM. 30 (4). pp. 729–735. doi:10.1145/2157.2158 

Read other articles:

Demografi Barbados

Piramida penduduk Barbados pada tahun 2020 Demografi Barbados merupakan pembahasan terkait kepadatan penduduk, etnis, tingkat pendidikan, kesehatan penduduk, status ekonomi, afiliasi keagamaan, dan aspek lain dari penduduk Barbados. Populasi Populasi Barbados (1960-2010). Piramida penduduk Barbados, menunjukkan struktur usia populasi. Pada sensus 2010 Barbados memiliki perkiraan populasi 277.821 jiwa.[1] Populasi yang ditabulasi hanya 226.193 karena undercount yang tinggi (diperkiraka...

 

Heo Jun (atlet anggar)

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. Heo JunHeo at the 2013 World Fencing ChampionshipsInformasi pribadiLahir31 Mei 1988 (umur 35)Seoul, Korea SelatanSenjataFloretTangankananTinggi badan1.68 mBerat badan58 kgPelatih tim nasionalJo Hui-jeKlubKlub Anggar GwangjuPeringkat FIEPeringkat ...

 

Fleuve

Pour les articles homonymes, voir Fleuve (homonymie). Le fleuve Gambie. Les bassins versants des principaux fleuves d'Europe. Fleuve est un mot pouvant sembler ambigu[1],[2],[3],[4] en français, où il désigne : un cours d'eau se jetant dans une mer ou un océan[5],[6],[1],[2],[4] ; un cours d'eau important aboutissant dans un désert (fleuve endoréique), comme le Tarim, « le plus long « fleuve intérieur » du monde »[7] ou l'Okavango ; un cours d'ea...

Curtiss BF2C Goshawk

United States Naval Biplane BF2C-1 Goshawk Curtiss BF2C-1 - Model 67A (on the right) Role Carrierborne Fighter and fighter-bomberType of aircraft National origin United States Manufacturer Curtiss Aeroplane and Motor Company Introduction 1933 Retired 1949 Primary users United States NavyRepublic of ChinaRoyal Thai Air ForceArgentine Air Force Produced October 1934 Number built 164 plus 2 prototypes Developed from Curtiss F11C Goshawk The Curtiss BF2C Goshawk (Model 67) was a United State...

 

1984 en science

Chronologies Données clés 1981 1982 1983  1984  1985 1986 1987Décennies :1950 1960 1970  1980  1990 2000 2010Siècles :XVIIIe XIXe  XXe  XXIe XXIIeMillénaires :-Ier Ier  IIe  IIIe Chronologies géographiques Afrique Afrique du Sud, Algérie, Angola, Bénin, Botswana, Burkina Faso, Burundi, Cameroun, Cap-Vert, République centrafricaine, Comores, République du Congo, République démocratique du Congo, Côte d'Ivoire, Djibouti, Égyp...

 

Rajesh Shringarpure

Indian television actor Rajesh ShringarpureShringarpure in 2017Born (1977-10-29) 29 October 1977 (age 46)[1]Mumbai, Maharashtra, IndiaOccupationActorYears active1995–presentSpouse Dimple Shringarpure ​(m. 2005)​[2] Rajesh Shringarpure (born 29 October 1977) is an Indian film and television actor who appears in Hindi cinema and Marathi cinema.He is currently playing the role of Malhar Rao Holkar in television serial Punyashlok Ahilyabai ...

Maison du parc naturel régional du Morvan

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. L'admissibilité de cette page est à vérifier (novembre 2023). Motif : Quelle notoriété encyclopédique ? Vous êtes invité à compléter l'article pour expliciter son admissibilité, en y apportant des sources secondaires de qualité, ainsi qu'à discuter de son admissibilité. Si rien n'est fait, cet article sera proposé au débat d'admissibilité un an au plus tard après la mise en place de ce...

 

大字 (数字)

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

 

Josip Štolcer-Slavenski

Josip Štolcer-SlavenskiBiographieNaissance 11 mai 1896ČakovecDécès 30 novembre 1955 (à 59 ans)BelgradeSépulture Nouveau cimetière de BelgradeNationalités serbecroateFormation Université de musique Franz-LisztActivités Compositeur, professeur de musiquemodifier - modifier le code - modifier Wikidata Monument Josip Štolcer-Slavenski dans le parc Zrinski à Čakovec Josip Štolcer-Slavenski (en cyrillique serbe : Јосип Штолцер-Славенски ; 11 mai 189...

斯洛博丹·米洛舍维奇

斯洛博丹·米洛舍维奇Слободан МилошевићSlobodan Milošević 南斯拉夫联盟共和国第3任总统任期1997年7月23日—2000年10月7日总理拉多耶·孔蒂奇莫米尔·布拉托维奇前任佐兰·利利奇（英语：Zoran Lilić）继任沃伊斯拉夫·科什图尼察第1任塞尔维亚总统任期1991年1月11日[注]—1997年7月23日总理德拉古京·泽莱诺维奇（英语：Dragutin Zelenović）拉多曼·博若维奇（英语：Radoman Bo...

 

土库曼斯坦总统

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

 

1260 in Ireland

List of events in the year 1260 ← 1259 1258 1257 1256 1255 1260 in Ireland → 1261 1262 1263 1264 1265 Centuries: 11th 12th 13th 14th 15th Decades: 1240s 1250s 1260s 1270s 1280s See also:Other events of 1260 List of years in Ireland Events from the year 1260 in Ireland. Incumbent Lord: Henry III Events Battle of Down; defeat and death of Brian O’Neill.[1] Grey Abbey in County Kildare was founded by William de Vesci. It was run by Franciscan friars. Births Roger Utlagh, or...

فتيات كشافة الولايات المتحدة

فتيات كشافة الولايات المتحدة فتيات كشافة الولايات المتحدة المقر نيويورك، نيويورك الدولة الولايات المتحدة الاحداثيات 40°45′03″N 73°59′00″W / 40.750833333333°N 73.983333333333°W / 40.750833333333; -73.983333333333   تاريخ التأسيس 12 مارس 1912 المؤسس جولييت جوردون لوو الأعضاء 2164318 الشباب 846600 البا...

 

بيرلينجتون (أونتاريو)

بيرلينجتون   الإحداثيات 43°19′30″N 79°48′00″W / 43.325°N 79.8°W / 43.325; -79.8   [1] تاريخ التأسيس 1874  تقسيم إداري  البلد كندا[2][3]  خصائص جغرافية  المساحة 185.66 كيلومتر مربع  ارتفاع 74 متر  عدد السكان  عدد السكان 186948 (2021)[4]  الكثافة السكانية 1...

 

Damon, Virginia

Unincorporated community in Virginia, United States This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Damon, Virginia – news · newspapers · books · scholar · JSTOR (January 2024)Unincorporated community in Virginia, United StatesDamonUnincorporated communityDamonLocation within the state of VirginiaS...

Scargo Lake

Scargo Lake is a fresh water kettle pond in Dennis, Massachusetts on Cape Cod. Scargo LakeScargo Lake from Scargo TowerScargo LakeShow map of MassachusettsScargo LakeShow map of the United StatesLocationDennis, Massachusetts, United StatesCoordinates41°44′35″N 70°11′00″W / 41.74306°N 70.18333°W / 41.74306; -70.18333TypeFreshPrimary outflowsSesuit CreekMax. length0.52 Miles (0.84 Kilometers)Surface area60 Acres (0.243 Kilometers)Average depth25 Feet (7.62 Me...

 

Reza Ghoochannejhad

Reza Ghoochannejhad Reza Ghoochanejhad 2014Informasi pribadiNama lengkap Reza Ghoochannejhad NourniaTanggal lahir 20 September 1987 (umur 26)Tempat lahir Mashhad, IranTinggi 1,80 m (5 ft 11 in)Posisi bermain Striker, SayapInformasi klubKlub saat ini Charlton AthleticNomor 8Karier junior LAC Frisia 1883 Cambuur1998-2005 HeerenveenKarier senior*Tahun Tim Tampil (Gol)2005-2009 Heerenveen 2 (0)2006-2007 → Go Ahead Eagles (pinjam) 13 (4)2009 → Emmen (pinjam) 12 (1)2009-2010 Go ...

 

Ледяное вино

Виноград для ледяного вина, замороженный на лозе Ледяное вино (также айсвайн[1]; нем. Eiswein) — дорогое коллекционное десертное вино с густым букетом, изготовляемое из винограда, замороженного на лозе. Изначально было специалитетом Германии и Австрии (как одно из п�...

Pierre-Cyrille Hautcœur

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (décembre 2022). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ». En pratique : Quelles sources sont attendues ?...

 

آديسون (ألاباما)

آديسون     الإحداثيات 34°12′06″N 87°10′36″W / 34.201653°N 87.176568°W / 34.201653; -87.176568   [1] تقسيم إداري  البلد الولايات المتحدة[2][3]  التقسيم الأعلى مقاطعة وينستون  خصائص جغرافية  المساحة 9.836709 كيلومتر مربع9.836712 كيلومتر مربع (1 أبريل 2010)  ارتفاع 233 مت�...