sábado, 21 de diciembre de 2019

TEORÍA DE TÉRMINOS DE GRAFOS


El símbolo primo ( ′ ), el símbolo primo doble ( ″ ), el símbolo primo triple ( ‴ ) y el símbolo primo cuádruple ( ⁗ ) se utilizan para designar unidades y para otros fines en matemáticas , ciencias, lingüística y música .
Aunque es similar en apariencia, el símbolo principal no debe confundirse con el apóstrofe ( 'o' ), comillas simples ), acento agudo ( ´ ) o acento grave ( ); el símbolo de doble prima no debe confundirse con la comilla doble ( “…” o "…" ), [1] la marca de ídem ( ” ) o la letra doble apóstrofe ( ˮ ). El primer símbolo es muy similar al hebreo geresh, pero en las fuentes modernas, el geresh está diseñado para alinearse con las letras hebreas y el símbolo principal no lo es, por lo que no deben intercambiarse. Todos estos símbolos de apariencia similar tienen significados diferentes, y sus códigos de caracteres son tratados de manera diferente por el software de composición y representación de fuentes.

principal
Doble primaTriple primaPrime cuádruple


Designación de unidades editar ]

El símbolo principal ( ′ ) se usa comúnmente para representar pies (ft) y minutos de arco (min de arco) . [2] Sin embargo, por conveniencia, se usa comúnmente una ( ) ( comilla simple ).
El doble cebado ( ″ ) representa pulgadas (in) y segundos de arco (arcsec) . [2] Sin embargo, por conveniencia, se usa comúnmente un ( ) ( comillas dobles ).
Por lo tanto, 3 ′ 5 ″ podría significar 3 pies y 5 pulgadas (de longitud), o 3 minutos y 5 segundos (de arco). Como medida angular, 3 ° 5 ′ 30 ″ significa 3 grados , 5 minutos de arco y 30 segundos de arco .
El triple cebado ( ‴ ) en la relojería representa una línea o 1/12 de pulgada. También se encuentra ocasionalmente en trabajos astronómicos históricos para denotar tercios ( 1 / 60 de un segundo de arco [3] [4] ). [5] [6]
Del mismo modo, un primer cuádruple ( ⁗ ) denota cuartas partes ( 1 / 60 de un tercer, aclaración necesaria ] una convención ya utilizado por Jamshid al-Kashi ). cita requerida ]

Uso en matemáticas, estadística y ciencias editar ]

En matemáticas, el primo generalmente se usa para generar nombres más variables para cosas que son similares, sin recurrir a subíndices: x 'generalmente significa algo relacionado o derivado de x . Por ejemplo, si un punto está representado por las coordenadas cartesianas x ,  y ) , entonces ese punto girado, traducido o reflejado podría representarse como x ',  y ') . El símbolo primo no está relacionado con los números primos .
Por lo general, el significado de x 'se define cuando se usa por primera vez, pero a veces se supone que se entiende su significado:
  • Una función derivada o diferenciada: f ′ ( x ) y f ″ ( x ) son la primera y segunda derivadas de f ( x ) con respecto a x . Del mismo modo son f ‴ ( x ) y f ⁗ ( x ). Del mismo modo, si y = f ( x ), entonces Y 'y Y "son la primera y segunda derivadas de y con respecto a x . (Existe otra notación)
  • Conjunto complemento : A 'es el complemento del conjunto A . (Existe otra notación)
  • La negación de un evento en la teoría de probabilidad: Pr ( A ') = 1 - Pr ( A ). (Existe otra notación)
  • El resultado de una transformación : Tx = x ′
  • La transposición de una matriz.
Se dice que la prima "decora" la letra a la que se aplica. La misma convención se adopta en la programación funcional , particularmente en Haskell .
En geometría , geografía y astronomía , primo y doble primo se usan como abreviaturas para minuto y segundo de arco (y, por lo tanto latitud , longitud , elevación y ascensión recta ).
En física , el primo se usa para denotar variables después de un evento. Por ejemplo, A 'indicaría la velocidad del objeto A después de un evento. También se usa comúnmente en relatividad: el evento en (x, y, z, t) en el cuadro S tiene coordenadas (x ', y', z ', t') en el cuadro S '.
En química , se usa para distinguir entre diferentes grupos funcionales conectados a un átomo en una molécula, como R y R ', que representan diferentes grupos alquilo en un compuesto orgánico . El carbono carbonílico en las proteínas se denota como C ', que lo distingue del otro carbono principal , el carbono alfa , que se denota como C α .
En biología molecular , la prima se usa para denotar las posiciones de carbono en un anillo de desoxirribosa o ribosa . Lo principal distingue los lugares en estos dos productos químicos, en lugar de los lugares en otras partes del ADN o ARN , como grupos fosfato o ácidos nucleicos . Por lo tanto, al indicar la dirección de movimiento de una enzimaA lo largo de una cadena de ADN, los biólogos dirán que se mueve desde el extremo 5 'hasta el extremo 3', porque estos carbonos están en los extremos de la molécula de ADN. La química de esta reacción exige que el 3 primer OH se extienda por la síntesis de ADN. Prime también se puede usar para indicar a qué posición se ha unido una molécula, como el 5'-monofosfato.

Uso en lingüística editar ]

El primo se puede usar en la transliteración de algunos idiomas , como los idiomas eslavos , para denotar la palatalización . Prime y double prime se usan para transliterar el yeri cirílico (el signo suave, ь) y el yer (el signo duro, ъ). [7] Sin embargo, en ISO 9 , se utilizan las letras modificadoras correspondientes.
Originalmente, la teoría de la barra X usaba una barra sobre unidades sintácticas para indicar los niveles de barra en la estructura sintáctica , generalmente representada como una barra superior . Si bien es fácil de escribir, la notación de barra resultó difícil de componer, lo que llevó a la adopción del símbolo principal para indicar una barra. (A pesar de la falta de barra, la unidad aún se leería como "barra X", en lugar de "X prime"). Con el desarrollo contemporáneo de software de composición tipográfica como LaTeX , las barras de composición tipográfica son considerablemente más simples; sin embargo, tanto los márgenes principales como los de barra son usos aceptados.
Algunas anotaciones de barra X usan un doble cebado (sustituyendo una barra doble) para indicar un nivel de frase, indicado en la mayoría de las anotaciones por "XP".

Usar en la notación Cubo de Rubik editar ]

En la notación de movimiento Cubo de Rubik, el cebado se usa para invertir movimientos o secuencias de movimiento (por ejemplo, L significa "girar la cara izquierda 90 grados en sentido horario", mientras que L ' significa "girar la cara izquierda 90 grados en sentido antihorario"). [8]

Uso en música editar ]


Cebado, cebado doble y cebado triple
El símbolo principal se usa en combinación con letras minúsculas en el sistema de notación de tono Helmholtz para distinguir las notas en diferentes octavas desde la C central hacia arriba. Por lo tanto, c representa la C debajo de la C central, c 'representa la C central, c ″ representa la C en la octava por encima de la C central, y c ‴ la C en la octava dos octavas por encima de la C. central Una combinación de letras mayúsculas y sub- los símbolos primos se usan para representar notas en octavas inferiores. Por lo tanto, C representa la C debajo del pentagrama de graves, mientras que C ͵ representa la C en la octava debajo de eso.
En algunas partituras musicales, el doble primo (″) se usa para indicar un período de tiempo en segundos. Se utiliza sobre una fermata (𝄐) que denota una nota larga o descanso.

Historia editar ]

El nombre "primo" es una especie de metonimia . A principios del siglo XX, la notación x 'se leía como "x prima" no porque fuera una x seguida de un "símbolo principal", sino porque era la primera de la serie que continuaba con x "(" x segundo ") yx ‴ (" x tercero "). Fue solo más tarde, en las décadas de 1950 y 1960, cuando el término "primo" comenzó a aplicarse al símbolo similar al apóstrofe . Aunque ahora es más común pronunciar x ″ y x ‴ como "x double prime" y "x triple prime", a veces se pronuncian a la antigua usanza como "x second" y "

Codificaciones de computadora editar ]


Cebado, cebado doble y cebado triple
Las representaciones Unicode y HTML de los símbolos primos y relacionados son las siguientes.
PersonajeUnicodeEntidad HTML
Prime ( ′ )U + 2032 
Doble prima ( ″ )U + 2033 
Triple prima ( ‴ )U + 2034
Prima invertida ( ‵ )U + 2035 
Doble prima invertida ( ‶ )U + 2036
Prima triple invertida ( ‷ )U + 2037
Cuádruple prima (⁗)U + 2057
Modificador de letra prima ( ʹ )U + 02B9ʹ
Modificador de letra doble prima ( ʺ )U + 02BAʺ
Los caracteres "modificador de letra prima" y "modificador de letra doble prima" están destinados a fines lingüísticos, como la indicación de énfasis o la transliteración de ciertos caracteres cirílicos .
Cuando el conjunto de caracteres utilizado no incluye el carácter de primo o doble primo (por ejemplo, ISO 8859-1 se asume comúnmente en IRC ) cita requerida ] , a menudo se aproximan respectivamente por apóstrofes y comillas normales o cursivas .
LaTeX proporciona un símbolo principal de gran tamaño, \prime(), que, cuando se usa en super o sub-scripts, se procesa adecuadamente; por ejemplo, f_\prime^\primeaparece comoUn apóstrofe, 'es un atajo para un superíndice primo; por ejemplo, f'aparece como.









  (Redirigido desde número acromático )

Coloración completa del gráfico Clebsch con 8 colores. Cada par de colores aparece en al menos un borde. No existe una coloración completa con más colores: en cualquier coloración 9, algún color aparecería solo en un vértice, y no habría suficientes vértices adyacentes para cubrir todos los pares que involucran ese color. Por lo tanto, el número acromático del gráfico de Clebsch es 8.
En la teoría de grafos , la coloración completa es lo opuesto a la coloración armoniosa en el sentido de que es una coloración de vértice en la que cada par de colores aparece en al menos un par de vértices adyacentes. De manera equivalente, una coloración completa es mínima en el sentido de que no se puede transformar en una coloración adecuada con menos colores fusionando pares de clases de colores. El número acromático ψ (G) de un gráfico G es el número máximo de colores posible en cualquier coloración completa de G.














Teoría de la complejidad editar ]

Encontrar ψ (G) es un problema de optimización . El problema de decisión para la coloración completa se puede expresar como:
INSTANCIA: un gráfico  y entero positivo 
PREGUNTA: ¿existe una partición de dentro o más conjuntos disjuntos tal que cada es un conjunto independiente para y tal que para cada par de conjuntos distintos  No es un conjunto independiente.
Determinar el número acromático es NP-duro ; determinar si es mayor que un número dado es NP-completo , como lo muestran Yannakakis y Gavril en 1978 mediante la transformación del problema de coincidencia máxima mínima. [1]
Tenga en cuenta que cualquier color de un gráfico con el número mínimo de colores debe ser un color completo, por lo que minimizar el número de colores en un color completo es solo una reafirmación del problema de color estándar del gráfico .

Algoritmos editar ]

Para cualquier k fijo , es posible determinar si el número acromático de un gráfico dado es al menos k , en tiempo lineal. [2]
El problema de optimización permite la aproximación y es aproximable dentro de un  relación de aproximación . [3]

Clases especiales de gráficos editar ]

La completitud NP del problema del número acromático también se aplica a algunas clases especiales de gráficos: gráficos bipartitos , [2] complementos de gráficos bipartitos (es decir, gráficos que no tienen un conjunto independiente de más de dos vértices), [1] gráficos e intervalos gráficos , [4] e incluso para árboles. [5]
Para complementos de árboles, el número acromático se puede calcular en tiempo polinómico. [6] Para los árboles, puede aproximarse a un factor constante. [3]
Se sabe que el número acromático de un gráfico hipercubo n- dimensional es proporcional a, pero la constante de proporcionalidad no se conoce con precisión.

No hay comentarios:

Publicar un comentario