Galería de gráficos con nombre

Ver también: Glosario de términos de teoría de grafos

Para obtener una cobertura más amplia de este tema, consulte Gráfico con nombre .

Algunas de las estructuras finitas consideradas en la teoría de grafos tienen nombres, a veces inspirados por la topología del grafo y, a veces, por su descubridor. Un ejemplo famoso es el gráfico de Petersen , un gráfico concreto en 10 vértices que aparece como un ejemplo mínimo o contraejemplo en muchos contextos diferentes.

Gráficos individuales

• 

  Balaban 10 jaulas

• 

  Balaban 11 jaulas

• 

  Cubo de bidiakis

• 

  Gráfico de Brinkmann

• 

  Gráfico de toros

• 

  Gráfico de mariposa

• 

  Gráfico de Chvátal

• 

  Gráfico de diamante

• 

  Gráfico de Durero

• 

  Gráfico de 54 Ellingham-Horton

• 

  Ellingham – Horton 78 gráficos

• 

  Gráfico de Errera

• 

  Gráfico de Franklin

• 

  Gráfico de Frucht

• Gráfico de Goldner-Harary

• Gráfico de Golomb

• Gráfico de Grötzsch

• Gráfico de Harries

• Gráfico de Harries-Wong

• Gráfico de Herschel

• Gráfico de Hoffman

• Gráfico de Holt

• Gráfico de horton

• Gráfico de Kittell

• Gráfico de Markström

• Gráfico de McGee

• Gráfico de Meredith

• Husillo Moser

• Gráfico de Sousselier

• Gráfico de Poussin

• Gráfico de Robertson

• Gráfico de Sylvester

• Fragmento de Tutte

• Gráfico de Tutte

• Gráfico de Young – Fibonacci

• Gráfico de Wagner

• Gráfico de pozos

• Gráfico de Wiener-Araya

Gráficos altamente simétricos

Gráficos muy regulares

El gráfico fuertemente regular en v vértices y rango k generalmente se denota srg ( v, k , λ, μ).

• Gráfico de Clebsch

• Gráfico de Cameron

• Gráfico de Petersen

• Gráfico de Hall-Janko

• Gráfico de Hoffman-Singleton

• Gráfico Higman-Sims

• Gráfico de Paley de orden 13

• Gráfico de Shrikhande

• Gráfico de Schläfli

• Gráfico de Brouwer-Haemers

• Gráfico local de McLaughlin

• Gráfico de Perkel

• Gráfico de Gewirtz

Gráficos simétricos

Un gráfico simétrico es aquel en el que hay una simetría ( automorfismo del gráfico ) que lleva cualquier par ordenado de vértices adyacentes a cualquier otro par ordenado; el censo de Foster enumera todos los pequeños gráficos simétricos de 3 regulares. Todo gráfico fuertemente regular es simétrico, pero no al revés.

• Gráfico Heawood

• Gráfico de Möbius-Kantor

• Gráfico de Pappus

• Gráfico de desargues

• Gráfico de Nauru

• Gráfico de Coxeter

• Gráfico de Tutte-Coxeter

• Gráfico de Dyck

• Gráfico de Klein

• Fomentar gráfico

• Gráfico de Biggs-Smith

• El gráfico de Rado

Gráficos semisimétricos

• Gráfico de Folkman

• Gráfico gris

• Gráfico de Liubliana

• Tutte 12 jaulas

Familias de gráficos

Gráficos completos

El gráfico completo de vértices se denomina a menudo -clique y se suele denotar del alemán komplett . ^[1]${\displaystyle n}$${\displaystyle n}$${\displaystyle K_{n}}$

• ${\displaystyle K_{1}}$

• ${\displaystyle K_{2}}$

• ${\displaystyle K_{3}}$

• ${\displaystyle K_{4}}$

• ${\displaystyle K_{5}}$

• ${\displaystyle K_{6}}$

• ${\displaystyle K_{7}}$

• ${\displaystyle K_{8}}$

Gráficos bipartitos completos

El gráfico bipartito completo generalmente se denota . Para ver la sección sobre gráficos de estrellas. El gráfico es igual al de 4 ciclos (el cuadrado) que se presenta a continuación. ${\displaystyle K_{n,m}}$${\displaystyle n=1}$${\displaystyle K_{2,2}}$${\displaystyle C_{4}}$

• ${\displaystyle K_{2,3}}$

• ${\displaystyle K_{3,3}}$, el gráfico de utilidad

• ${\displaystyle K_{2,4}}$

• ${\displaystyle K_{3,4}}$

Ciclos

El gráfico de ciclo en vértices se llama ciclo n y generalmente se denota . También se le llama gráfico cíclico , polígono o n-gon . Los casos especiales son el triángulo , el cuadrado y luego varios con nombres griegos como pentágono , hexágono , etc.${\displaystyle n}$${\displaystyle C_{n}}$ ${\displaystyle C_{3}}$ ${\displaystyle C_{4}}$ ${\displaystyle C_{5}}$ ${\displaystyle C_{6}}$

• ${\displaystyle C_{3}}$

• ${\displaystyle C_{4}}$

• ${\displaystyle C_{5}}$

• ${\displaystyle C_{6}}$

Gráficos de amistad

El gráfico de amistad F _n se puede construir uniendo n copias del gráfico de ciclo C ₃ con un vértice común. ^[2]

Las gráficas de amistad F ₂ , F ₃ y F ₄ .

Gráficos de fullereno

En la teoría de grafos, el término fullereno se refiere a cualquier 3- regulares , grafo plano con todas las caras de tamaño 5 o 6 (incluyendo la cara externa). Se deduce de la fórmula del poliedro de Euler , V  -  E  +  F  = 2 (donde V , E , F indican el número de vértices, aristas y caras), que hay exactamente 12 pentágonos en un fullereno y h  =  V / 2 - 10 hexágonos. Por tanto, V  = 20 + 2 h ; E  = 30 + 3 h . Las gráficas de fullereno son lasRepresentaciones de Schlegel de los correspondientes compuestos de fullereno.

• 20-fullereno ( gráfico dodecaédrico )

• 24-fullereno ( gráfico trapezoedro truncado hexagonal )

• Gráfico de 26 fullereno

• 60-fullereno ( gráfico icosaédrico truncado )

• 70-fullereno

G. Brinkmann y A. Dress han desarrollado un algoritmo para generar todos los fullerenos no isomórficos con un número dado de caras hexagonales. ^[3] G. Brinkmann también proporcionó una implementación de libre acceso, llamada fullgen .

Sólidos platónicos

El gráfico completo en cuatro vértices forma el esqueleto del tetraedro y, de manera más general, los gráficos completos forman esqueletos de simples . Los gráficos de hipercubo también son esqueletos de politopos regulares de dimensiones superiores .

• cubo ,
  ${\displaystyle n=8}$${\displaystyle m=12}$

• octaedro ,
  ${\displaystyle n=6}$${\displaystyle m=12}$

• dodecaedro ,
  ${\displaystyle n=20}$${\displaystyle m=30}$

• Icosaedro ,
  ${\displaystyle n=12}$${\displaystyle m=30}$

Sólidos truncados

• Tetraedro truncado

• Cubo truncado

• Octaedro truncado

• Dodecaedro truncado

• Icosaedro truncado

Snarks

Un snark es un gráfico cúbico sin puentes que requiere cuatro colores en cualquier color de borde adecuado . El snark más pequeño es el gráfico de Petersen , ya mencionado anteriormente.

• Blanuša snark (primero)

• Blanuša snark (segundo)

• Snark de doble estrella

• Flor snark

• Loupekine snark (primero)

• Loupekine snark (segundo)

• Szekeres snark

• Gráfico de Tietze

• Watkins snark

Estrella

Una estrella S _k es el gráfico bipartito completo K _{1, k} . La estrella S ₃ se llama gráfico en garra.

Los gráficos de estrellas S ₃ , S ₄ , S ₅ y S ₆ .

Gráficos de rueda

El gráfico de rueda W _n es un gráfico de n vértices construido conectando un solo vértice a cada vértice en un  ciclo ( n - 1).

Ruedas - .${\displaystyle W_{4}}$${\displaystyle W_{9}}$

Referencias

1. David Gries y Fred B. Schneider, Un enfoque lógico de las matemáticas discretas , Springer, 1993, p 436.
2. Gallian, JA "Dynamic Survey DS6: Graph Labeling". Electronic Journal of Combinatorics , DS6, 1-58, 3 de enero de 2007. [1] Archivado el 31 de enero de 2012en Wayback Machine .
3. Brinkmann, Gunnar; Vestido, Andreas WM (1997). "Una enumeración constructiva de fullerenos". Revista de algoritmos . 23 (2): 345–358. doi : 10.1006 / jagm.1996.0806 . Señor  1441972 .