Continuous graph

This article is about sets of vertices and edges (graphs) defined on a continuous space. For graphs of continuous functions, see Continuous function.

For connected graphs, see Connectivity (graph theory).

A continuous graph is a graph whose set of vertices is a continuous space X. Edges are then defined by a function from the cartesian product X² to the set {0, 1}. This could represent 1 for an edge between two vertices, and 0 for no edge, or it could represent a complete graph with a 2-color edge coloring. In this context, the set {0,1} is often denoted by 2, so we have f(X²)→2. For multi-colorings of edges we would have f(X²)→n.^[1][2][3] Continuous graphs have applications to peer-to-peer systems.^[4]

A graph limit or graphon is the limit of a sequence of graphs. Such a limit is a symmetric measurable function in two variables^[5], that can often be written f(S²)→[0,1] which is the same as a complete continuous graph where the edges have values in the interval [0,1].

For any sets X and Y, the two-variable function f(X²)→Y is a complete graph with edges labelled with elements of Y. For multi-variable functions we have f(Xⁿ)→Y for the complete hypergraph with edges labelled with elements of Y.^[6]

Given a discrete-time dynamical system, the trajectories, or orbits (state space) of all the points form a (possibly disconnected) directed graph which is a continuous graph if the system is defined on a continuous space. The trajectories of a continuous-time dynamical system would form a collection of curved paths (phase space) rather than a collection of piece-wise linear paths and so is not a graph in the traditional sense.

See also

• Tree (set theory)
• Petri Net#Discrete, continuous, and hybrid Petri nets

References

1. ^ CONTINUOUS GRAPHS AND C*-ALGEBRAS, VALENTIN DEACONU, Operator theoretical methods: 17th International Conference on Operator Theory, Timișoara (Romania), July 23-26, 1998, ISBN 978-973-99097-2-3.
2. ^ CONTINUOUS RAMSEY THEORY ON POLISH SPACES AND COVERING THE PLANE BY FUNCTIONS, STEFAN GESCHKE, MARTIN GOLDSTERN, AND MENACHEM KOJMAN, Journal of Mathematical Logic, 2004.
3. ^ INFINITE RAMSEY THEORY, STEFAN GESCHKE.
4. ^ Novel architectures for P2P applications: the continuous-discrete approach, M Naor, U Wieder - ACM Transactions on Algorithms (TALG), 2007.
5. ^ Graph Limits and Parameter Testing, Christian Borgs, Jennifer Chayes, László Lovász, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, 2006
6. ^ Testability and repair of hereditary hypergraph properties, T Austin, T Tao - Random Structures and Algorithms, 2010

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Combinatorics stubs Graph theory Wikimedia Foundation. 2010. Игры ⚽ Нужен реферат? Continuous geometry Continuous inspection Look at other dictionaries: Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia continuous — /kənˈtɪnjuəs/ (say kuhn tinyoohuhs) adjective 1. having the parts in immediate connection, unbroken. 2. uninterrupted in time; without cessation. 3. Grammar denoting a verb aspect, or other verb category, which indicates action or state going on… …   Continuous wavelet transform — of frequency breakdown signal. Used symlet with 5 vanishing moments. A continuous wavelet transform (CWT) is used to divide a continuous time function into wavelets. Unlike Fourier transform, the continuous wavelet transform possesses the ability …   Wikipedia Graph — (gr[.a]f), n. [See { graph}.] (Math.) 1. A curve or surface, the locus of a point whose co[ o]rdinates are the variables in the equation of the locus; as, a graph of the exponential function. [Webster 1913 Suppl.] 2. A diagram symbolizing a… …   The Collaborative International Dictionary of English Continuous function — Topics in Calculus Fundamental theorem Limits of functions Continuity Mean value theorem Differential calculus  Derivative Change of variables Implicit differentiation Taylor s theorem Related rates …   Wikipedia Continuous-time quantum walk — A Continuous time quantum walk (CTQW) is a walk on a given connected graph that is dictated by a time varying unitary matrix that relies on the Hamiltonian of the quantum system and the adjacency matrix. CTQW belongs to what is known as Quantum… …   Wikipedia Continuous-repayment mortgage — Analogous to continuous compounding, a continuous annuity[1][2] is an ordinary annuity in which the payment interval is narrowed indefinitely. A (theoretical) continuous repayment mortgage is a mortgage loan paid by means of a continuous annuity …   Wikipedia Graph continuous — In mathematics, and in particular the study of game theory, a function is graph continuous if it exhibits the following properties. The concept was originally defined by Partha Dasgupta and Eric Maskin in 1986 and is a version of continuity that… …   Wikipedia Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia Continuous-time Markov process — In probability theory, a continuous time Markov process is a stochastic process { X(t) : t ≥ 0 } that satisfies the Markov property and takes values from a set called the state space; it is the continuous time version of a Markov chain. The… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”