Cómo utilizar y expresar eficientemente el análisis de red
El análisis de redes es una rama importante de la investigación de operaciones, que utiliza principalmente la teoría de grafos para estudiar la estructura y optimización de varias redes.
El análisis de redes es uno de los métodos indispensables e importantes en geografía cuantitativa.
El contenido principal de este capítulo:
Descripción de la teoría de grafos de la red geográfica
Problema de ubicación y camino más corto
Flujo máximo y mínimo flujo de costos
Sección 1: Descripción de la red geográfica en teoría de grafos
En el sentido popular, "mapa" se refiere principalmente a varios mapas, imágenes de teledetección o representados por varios símbolos y palabras. Diagramas esquemáticos, o gráficos, histogramas, etc. extraídos de diversos datos geográficos.
La "grafica" en la teoría de grafos es un concepto matemático. Este tipo de "mapa" puede revelar el patrón de distribución espacial de entidades y objetos geográficos, las relaciones mutuas entre elementos geográficos, sus formas de movimiento en el espacio regional, la secuencia de ocurrencia de eventos geográficos, etc.
1. Descripción de la red geográfica en la teoría de grafos
(1) Gráfico: Supongamos que V está compuesto por n puntos VI (I = 1, 2,..., n), que es V = {V1, V2,...,VN} y E es el conjunto formado por m líneas EI (I = 1). No hay dos rectas que tengan un punto común distinto de sus extremos.
(1) Definición de gráfico
Entonces, V y E se combinan para formar un gráfico G, denotado como G = (V, E).
(3) Arista: Cada línea en E se llama arista (o arco) del gráfico G; si una arista E conecta dos vértices de U y V, se registra como E = (u, V). ).
(2) Vértice: Cada punto VI (I = 1, 2,...,n) se llama vértice del gráfico g.
(4) En el gráfico G= En (V, E), no se permite que V sea un conjunto vacío, pero E puede ser un conjunto vacío.
(5) De la definición anterior, se puede ver que el gráfico contiene dos elementos básicos:
① Conjunto de puntos (o conjunto de vértices ② Conjunto de bordes (o conjunto de arcos); ).
Por ejemplo: En el gráfico que se muestra en la Figura 10.1.1,
El conjunto de vértices es v = {v1, v2, v3, v4, V5, v6, V7, V8} ,
El conjunto de aristas es e = {e1, E2, E3, E4, E5, e6, E7, E8, E9,
e10, e11}.
Figura 1.1.1
(6) En un sistema geográfico realista, la ubicación geográfica, las entidades geográficas, las áreas geográficas y sus interrelaciones se pueden simplificar y abstraer hasta cierto punto. una red geográfica en el sentido de la teoría de grafos, es decir, un grafo.
Ubicación geográfica, entidad geográfica, área geográfica, como cima de una montaña, intersección de ríos, estación, muelle, aldea, pueblo, etc.
Sus interrelaciones, como líneas estructurales, ríos, líneas de transporte, líneas de suministro de energía y comunicación, flujo de población, flujo de materiales, flujo de capital, flujo de información, flujo de tecnología, etc. ——La conexión entre puntos.
Un sistema de relieve de cuenca complejo compuesto por unidades de relieve de cuenca básicas. Si se descartan varios accidentes geográficos complejos, el final básico (árbol) de cada línea de río, bifurcación o confluencia de río, el sistema de relieve de cuenca - sistema de agua.
Leonard Euler - El problema de los siete puentes
La ciudad de Konigsberg en Prusia Oriental (ahora Kaliningrado) fue construida sobre dos ríos y dos puentes en el río La intersección de dos pequeñas islas. . * * * Hay siete pequeños puentes que conectan las dos islas y la isla con el resto de la ciudad. Entonces, ¿pueden los habitantes de Königsberg regresar a su lugar original, siempre que crucen cada pequeño puente? Los resultados de la investigación en teoría de grafos nos dicen que la respuesta es no. .
(7) Cabe señalar que la definición de gráfico solo se centra en si los puntos están conectados, pero no en el método de conexión entre puntos. Su forma de dibujar no es exclusiva de ninguna figura.
(2) Algunos conceptos relacionados de gráficos
(1) Gráficos no dirigidos y gráficos dirigidos
Gráficos no dirigidos: cada borde del gráfico no está dado dirección,
Es decir, (u, v) = (v, u);
Gráfico dirigido: cada borde del gráfico tiene una dirección,
p>
Es decir, (u, v) ≦ (v, u).
Generalmente, el conjunto de aristas de un gráfico dirigido se denota como A, y el conjunto de aristas de un gráfico no dirigido se denota como E. De esta manera, G=(V, A) representa un gráfico dirigido, y G=(V, E) representa un gráfico no dirigido.
Gráfico dirigido
(2) Gráfico ponderado.
Si a cada arista (vi, vj) del gráfico G = (V, E) se le asigna un valor wij, entonces a G se le llama gráfico ponderado, donde wij se llama arista (vi, vj). ) peso.
Además de ponderar los bordes del gráfico, también puedes ponderar los vértices del gráfico. Es decir, para cada vértice vj del gráfico G también se puede dar una carga a(vj).
(3) Aristas asociadas.
Si e=(u, v), entonces u y v son los puntos finales del borde e, y e es el borde asociado de u y v.
(4) Anillo.
Si los dos extremos de e son iguales, es decir, u=v, se llama anillo.
(5) Múltiples aristas.
Si hay múltiples aristas que conectan dos puntos finales, se denomina aristas múltiples.
(6) Múltiples gráficos.
Un gráfico con múltiples aristas se llama multigrafo.
(7)Diagrama simple.
Un gráfico sin ciclos y con múltiples aristas se llama gráfico simple.
(8) Punto y tiempo.
El número de lados con el punto V como punto final se llama grado del punto V y se registra como d(v).
Los puntos con grado igual a 1 se denominan puntos colgantes; los puntos asociados con puntos colgantes se denominan bordes colgantes.
Los puntos con grado cero se denominan puntos aislados y los puntos con grados impares; llamado Singularidad. Los puntos pares se llaman puntos pares.
(9) Gráfico conectado. En el gráfico G, si hay al menos un camino entre dos puntos cualesquiera (para gráficos dirigidos, no se considera la dirección de los bordes), entonces G se llama gráfico conectado; de lo contrario, se llama gráfico desconectado.
(10) Camino (cadena).
Si en el gráfico G=(V, E), si los vértices y las aristas aparecen alternativamente (para un gráfico dirigido, los vértices antes y después de cada arista deben ser el punto inicial y final de el borde respectivamente):
P={vi1, ei1, vi2, ei2,…, eik-1, vik}
Satisfacer
eit = (vit , vi, t+1 ) (t=1, 2,...,k-1)
p se llama camino (o cadena) de vi1 a vik, abreviado como
P={vi1, vi2,…,vik}.
(11) Bucle.
Si el punto inicial y final de una carretera son iguales, es decir, vi1=vik, se llama bucle.
(12)Árbol.
Un grafo no dirigido conectado y sin bucles se llama árbol.
(13)Dibujos básicos.
La gráfica no dirigida que se obtiene eliminando todas las flechas de una gráfica dirigida D=(V, A) se llama gráfica básica de D, y se llama G(D).
Parte (14).
Si eliminar un conjunto de aristas de un gráfico aumenta el número de subgrafos, las aristas eliminadas se denominan cortes.
(15) Subimagen.
Supongamos que G=(V, E) es un grafo no dirigido, V1 y E1 son subconjuntos de V y E respectivamente, es decir, V1 y E 1. Si hay ei∈E1, ambos puntos finales pertenecen a V 1.
(16)Subimágenes de soporte.
Supongamos que G1=(V1, E1) es un subgrafo del gráfico G=(V, E). Si V1 = V, entonces se dice que G1 es g.
(17) Árbol de soporte.
Supongamos que G=(V, E) es un grafo no dirigido. Si T = (V1, E1) es el subgrafo generador de G y T es un árbol, entonces se dice que T es el árbol generador de G.
(18) El peso del árbol.
La suma de los pesos de todos los lados del árbol se llama peso del árbol.
(19) Árbol de expansión mínimo.
Entre todos los árboles de expansión de un gráfico, el árbol de expansión con el peso más pequeño se denomina árbol de expansión mínimo del gráfico.
2. Medición de redes geográficas
Muchos problemas geográficos prácticos pueden describirse como redes geográficas en el sentido de la teoría de grafos, la disposición de puntos y líneas, y su topología, conectividad y La complejidad se puede medir además cuantitativamente.
Dendrítica
Red geográfica
Red plana (bidimensional)
Red no plana (no bidimensional)
Tipo de carretera
Anillo
Tipo de celda
Figura 10.1.5 Clasificación de topología de red geográfica
Red geográfica actual topología La red plana bidimensional más comúnmente estudiada basada en la descripción de un gráfico plano es la más común.
El llamado plano se define como: las líneas de conexión no pueden cruzarse entre sí, y cada línea de conexión no puede tener otros puntos comunes excepto el vértice (Niu Wenyuan, 1987).
A menos que se indique lo contrario, la siguiente discusión se limita a redes planas bidimensionales.
Matriz de asociación y matriz de adyacencia
Matriz de asociación: mide la asociación entre vértices y aristas en un gráfico de red.
Supongamos que el conjunto de vértices del gráfico de red G=(V, E) es V={v1, v2,...,vn}, y el conjunto de aristas es E={e1, e2, ..., em}, entonces la red La matriz de asociación del gráfico es una matriz n×m, que se puede expresar como:
Gij es el número de veces que el vértice vi está asociado con el borde ej.
v3
v1
v2
v4
v5
e1
e2
e3
e4
e5
e6
e7
La matriz de correlación para este gráfico es:
Ejemplo:
Matriz de adyacencia: mide la conectividad entre los vértices en un gráfico de red.
Supongamos que el conjunto de vértices del gráfico G=(V, E) es V={v1, v2,..., vn}, entonces la matriz de adyacencia es una matriz cuadrada de n orden, que se puede expresar como:
Aij representa el número de aristas que conectan los vértices vi y vj.
La matriz de adyacencia del gráfico es:
v3
v1
v2
v4
v5
e1
e2
e3
e4
e5
e6
e7
Ejemplo:
(2) Indicadores de medición relacionados
Índice β
Ciclo número k
Índice α
Índice γ
Para cualquier diagrama de red, existen tres indicadores básicos:
①Líneas de conexión (bordes o arcos) ) número m;
②El número de nodos (vértices) n;
③El número de subgrafos en la red p.
Pueden producir lo siguiente Indicadores de medición más generales:
(1) Índice Beta
◣◣◣◣◣◣◣◣◣◣◣◣◣◣◣◣◣◣◣◣𗫧◣𗫧𗫧◣◣ 𗫧96999
◣β=0, lo que indica que no hay red a medida que aumenta la complejidad de la red, el valor β también aumenta;
◣Para una red sin puntos aislados, si el número de conexiones es n-p, el índice β es
Si la red geográfica no contiene subgrafos de segundo nivel, es decir, P =1, entonces su valor mínimo del indicador de conexión es.
(2) Ciclo número k
Un ciclo es un camino cerrado, y su punto inicial es también el punto final.
◣Si hay un bucle en la red, el número de conexiones debe exceder n-p (el número mínimo de conexiones en la red).
◣El número de bucles k: el número real de conexiones menos el número mínimo de conexiones, es decir,
(3) índice
◣El índice - el número real de bucles y la red La relación entre el número máximo de bucles que pueden existir en .
◣El número máximo de bucles que pueden existir en la red es el número máximo de conexiones menos el número mínimo de conexiones, es decir,
Entonces, el exponente es
Este exponente también se puede expresar como porcentaje
Para redes no planas, el índice es
El rango cambiante del índice generalmente está entre [0, 1], = 0 significa que no hay ningún bucle en la red; =1, indica que se ha alcanzado el número máximo de bucles en la red.
◣
◣
(4) índice γ
◣ índice γ: el número real de conexiones en la red y el máximo posible conexión Relación numérica. Para redes planas, la fórmula de cálculo es:
El índice gamma también se puede expresar como porcentaje.
◣ El índice γ es un indicador de conectividad de red, y su rango de valores es [0, 1].
◣γ=0, lo que significa que no hay conexiones en la red, solo puntos aislados
γ=1, lo que significa que cada nodo de la red está conectado a todos; otros nodos.