Gráfico – Notas leídas

Gráfico . Abstracción matemática definida por la relación G = o V es el conjunto de nodos o vértices y A es el conjunto de pares que definen los arcos o aristas que unen pares de vértices o bucles si unen un vértice consigo mismo.

Resumen

[ hide ]

  • 1. Orígenes
  • 2
    • 1 gráfico dirigido.
    • 2 Pedido.
    • 3 Ruta.
    • 4 ciclos.
    • 5 Matriz de contigüidad.
  • 3 gráficos notables.
  • 4 Véase también.
  • 5

Fondo

Euler fue el primero en referirse a los gráficos y utilizar algún tipo de teoría en la publicación. “Solutio problematis ad geometriam situs relevanteis” de 1736 para solucionar el problema de los puentes de Königsberg (ahora Kaliningrado), concluyendo que era imposible atravesar todos los ríos, pasando por todos los puentes, sin repetir ninguno y a partir de ahí, se formó también el concepto de grafo euleriano.

Definiciones

Gráfico gramo se entiende como la pareja o V es el conjunto de nodos o vértices {v 1 , v 2 ,…, V k ,…} y A es el conjunto de pares {v I , v j } , tal que v I y v j pertenecer V , que definen las aristas que unen pares de vértices o rizado si unen un vértice consigo mismo.

No dirigido Dónde gráfico no dirigido en este caso corresponde a la definición de un gráfico .

Gráfico orientado.

La definición de grafo dirigido y la de grafo son solo distantes en un aspecto que, en lugar de aristas, tiene arcos que son representados por los autores como (v I , v j ) Dónde I , v j > ya diferencia de la notación conyuntual, están ordenados, lo que implica que la relación se establece solo en el sentido de que los nodos aparecen en el arco.

Desde un punto de vista gráfico, los arcos tienen una orientación indicada por una flecha al final del nodo de destino, en el lado de salida no tiene nada.

Pedido.

Por orden del gráfico queremos decir G = , definido como | G | , al resultado | G | = | V | .

La carretera.

En un grafico G = a sendero entre los nodos v I y v j es una secuencia ordenada de nodos v I , v k1 , v k2 ,…, V j indicando que entre v I y v k1 hay una ventaja, que entre v k1 y v k2 hay una ventaja y así sucesivamente hasta que llegamos a v j .

Ciclo.

A ciclo es un camino que comienza y termina en el mismo nodo.

Matriz de contigüidad.

Dado un gráfico G = pedido NO, está asociado con una matriz de adyacencia METRO cuadrado NxN donde cada fila y columna está asociada con cada nodo específico y las celdas contienen el número de bordes entre el nodo de la fila y el nodo que identifica la columna.

En el caso de gráficos no dirigidos, la matriz de adyacencia es simétrica ya que los bordes identifican un flujo bidireccional. En los dígrafos, los arcos no son bidireccionales, por lo que la matriz no tiene por qué serlo.

La matriz también ayuda a representar gráficos, ya que contiene información de los nodos y los bordes entre ellos, lo que la hace ideal para representaciones por computadora.

Gráficos notables.

En los gráficos, hay una gran colección de gráficos llamados notables.

  • Gráfico nulo: es el gráfico sin nodos.
  • Gráfico vacío: este es el gráfico que no tiene bordes.
  • Gráfico unitario o trivial: Tiene un solo nodo sin enlaces.
  • Gráfico simple: es el gráfico sin enlaces.
  • Gráfico asociado: Es el gráfico donde entre cualquier par de vértices hay un camino para viajar entre ellos.
  • Gráfico completo: gráfico donde hay un borde (o un arco si está orientado) entre cualquier par de vértices diferentes.
  • Kn: Es el gráfico de orden simple completo. metro.
  • Gráfico de dos partes: es el gráfico tal que todo Vlos nodos se pueden separar en V 1 y V 2 sin coincidencias entre los dos, donde cada borde de sonido tiene un final en V 1 y otro en V 2 .
  • Grafo bipartito completo: Es un grafo bipartito tal que cada nodo de V 1se une a todos los de V 2 .
  • Gráfico plano: Es el gráfico que se puede representar en un plano sin que ningún borde (o arco) se cruce con otro.
  • Árbol: gráfico conectado sin ciclos.
  • Gráfico euleriano: gráfico que tiene caminos eulerianos

Deja un comentario