Faster access than browser!
75 relations: A* search algorithm, Approximation algorithm, Augmented tree-based routing, Axiom of choice, Bond graph, Breadth-first search, Cayley's formula, Choice function, Complete bipartite graph, Complete graph, Computational complexity theory, Connected component (graph theory), Connected dominating set, Connectivity (graph theory), Cycle (graph theory), Cycle basis, Cycle graph, Cycle space, Data link layer, Delaunay triangulation, Depth-first search, Determinant, Dijkstra's algorithm, Dual matroid, Edge contraction, Euclidean minimum spanning tree, Family of sets, Flooding algorithm, Genus (mathematics), Glossary of graph theory terms, Good spanning tree, Graduate Texts in Mathematics, Graph (discrete mathematics), Graph embedding, Graph theory, Graphic matroid, Hamiltonian path problem, Hypercube graph, Invariant (mathematics), Invertible matrix, Kirchhoff's theorem, Link-state routing protocol, Loop-erased random walk, Mathematics, Matrix (mathematics), Matroid, Mesh networking, Minimum degree spanning tree, Minimum spanning tree, Multigraph, ..., Open Shortest Path First, Pathfinding, Planar graph, Proofs from THE BOOK, Queue (abstract data type), Random minimum spanning tree, Randomness, Routing loop problem, Sharp-P-complete, SIAM Journal on Computing, Spanning Tree Protocol, Springer Science+Business Media, Stack (abstract data type), Switching loop, Symposium on Theory of Computing, Telecommunications network, Time complexity, Topological graph theory, Trémaux tree, Tree (graph theory), Tutte polynomial, Two-dimensional space, Vertex (graph theory), Xuong tree, Zorn's lemma. Expand index (25 more) »
A* search algorithm
In computer science, A* (pronounced as "A star") is a computer algorithm that is widely used in pathfinding and graph traversal, which is the process of plotting an efficiently directed path between multiple points, called "nodes".
New!!: Spanning tree and A* search algorithm · See more »
Approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to NP-hard optimization problems with provable guarantees on the distance of the returned solution to the optimal one.
New!!: Spanning tree and Approximation algorithm · See more »
Augmented tree-based routing
Augmented tree-based routing (ATR) protocol, first proposed in Augmented Tree-based Routing Protocol for Scalable Ad Hoc Networks, Proc.
New!!: Spanning tree and Augmented tree-based routing · See more »
Axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that the Cartesian product of a collection of non-empty sets is non-empty.
New!!: Spanning tree and Axiom of choice · See more »
Bond graph
A bond graph is a graphical representation of a physical dynamic system.
New!!: Spanning tree and Bond graph · See more »
Breadth-first search
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures.
New!!: Spanning tree and Breadth-first search · See more »
Cayley's formula
In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley.
New!!: Spanning tree and Cayley's formula · See more »
Choice function
A choice function (selector, selection) is a mathematical function f that is defined on some collection X of nonempty sets and assigns to each set S in that collection some element f(S) of S. In other words, f is a choice function for X if and only if it belongs to the direct product of X.
New!!: Spanning tree and Choice function · See more »
Complete bipartite graph
No description.
New!!: Spanning tree and Complete bipartite graph · See more »
Complete graph
No description.
New!!: Spanning tree and Complete graph · See more »
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.
New!!: Spanning tree and Computational complexity theory · See more »
Connected component (graph theory)
In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
New!!: Spanning tree and Connected component (graph theory) · See more »
Connected dominating set
In graph theory, a connected dominated set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph.
New!!: Spanning tree and Connected dominating set · See more »
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to disconnect the remaining nodes from each other.
New!!: Spanning tree and Connectivity (graph theory) · See more »
Cycle (graph theory)
In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself.
New!!: Spanning tree and Cycle (graph theory) · See more »
Cycle basis
In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph.
New!!: Spanning tree and Cycle basis · See more »
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain.
New!!: Spanning tree and Cycle graph · See more »
Cycle space
In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its Eulerian subgraphs.
New!!: Spanning tree and Cycle space · See more »
Data link layer
The data link layer, or layer 2, is the second layer of the seven-layer OSI model of computer networking.
New!!: Spanning tree and Data link layer · See more »
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P).
New!!: Spanning tree and Delaunay triangulation · See more »
Depth-first search
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.
New!!: Spanning tree and Depth-first search · See more »
Determinant
In linear algebra, the determinant is a value that can be computed from the elements of a square matrix.
New!!: Spanning tree and Determinant · See more »
Dijkstra's algorithm
Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.
New!!: Spanning tree and Dijkstra's algorithm · See more »
Dual matroid
In matroid theory, the dual of a matroid M is another matroid M^\ast that has the same elements as M, and in which a set is independent if and only if M has a basis set disjoint from it.
New!!: Spanning tree and Dual matroid · See more »
Edge contraction
In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices that it previously joined.
New!!: Spanning tree and Edge contraction · See more »
Euclidean minimum spanning tree
The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane (or more generally in ℝd), where the weight of the edge between each pair of points is the Euclidean distance between those two points.
New!!: Spanning tree and Euclidean minimum spanning tree · See more »
Family of sets
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets.
New!!: Spanning tree and Family of sets · See more »
Flooding algorithm
A flooding algorithm is an algorithm for distributing material to every part of a graph.
New!!: Spanning tree and Flooding algorithm · See more »
Genus (mathematics)
In mathematics, genus (plural genera) has a few different, but closely related, meanings.
New!!: Spanning tree and Genus (mathematics) · See more »
Glossary of graph theory terms
This is a glossary of graph theory terms.
New!!: Spanning tree and Glossary of graph theory terms · See more »
Good spanning tree
In the mathematical field of graph theory, a good spanning tree T of an embedded planar graph G is a rooted spanning tree of G whose non-tree edges satisfy the following conditions.
New!!: Spanning tree and Good spanning tree · See more »
Graduate Texts in Mathematics
Graduate Texts in Mathematics (GTM) (ISSN 0072-5285) is a series of graduate-level textbooks in mathematics published by Springer-Verlag.
New!!: Spanning tree and Graduate Texts in Mathematics · See more »
Graph (discrete mathematics)
In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".
New!!: Spanning tree and Graph (discrete mathematics) · See more »
Graph embedding
In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (homeomorphic images of) are associated with edges in such a way that.
New!!: Spanning tree and Graph embedding · See more »
Graph theory
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
New!!: Spanning tree and Graph theory · See more »
Graphic matroid
In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given undirected graph.
New!!: Spanning tree and Graphic matroid · See more »
Hamiltonian path problem
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected).
New!!: Spanning tree and Hamiltonian path problem · See more »
Hypercube graph
In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube.
New!!: Spanning tree and Hypercube graph · See more »
Invariant (mathematics)
In mathematics, an invariant is a property, held by a class of mathematical objects, which remains unchanged when transformations of a certain type are applied to the objects.
New!!: Spanning tree and Invariant (mathematics) · See more »
Invertible matrix
In linear algebra, an n-by-n square matrix A is called invertible (also nonsingular or nondegenerate) if there exists an n-by-n square matrix B such that where In denotes the n-by-n identity matrix and the multiplication used is ordinary matrix multiplication.
New!!: Spanning tree and Invertible matrix · See more »
Kirchhoff's theorem
In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time as the determinant of a matrix derived from the graph.
New!!: Spanning tree and Kirchhoff's theorem · See more »
Link-state routing protocol
Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the other being distance-vector routing protocols.
New!!: Spanning tree and Link-state routing protocol · See more »
Loop-erased random walk
In mathematics, loop-erased random walk is a model for a random simple path with important applications in combinatorics and, in physics, quantum field theory.
New!!: Spanning tree and Loop-erased random walk · See more »
Mathematics
Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.
New!!: Spanning tree and Mathematics · See more »
Matrix (mathematics)
In mathematics, a matrix (plural: matrices) is a rectangular array of numbers, symbols, or expressions, arranged in rows and columns.
New!!: Spanning tree and Matrix (mathematics) · See more »
Matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces.
New!!: Spanning tree and Matroid · See more »
Mesh networking
A mesh network is a local network topology in which the infrastructure nodes (i.e. bridges, switches and other infrastructure devices) connect directly, dynamically and non-hierarchically to as many other nodes as possible and cooperate with one another to efficiently route data from/to clients.
New!!: Spanning tree and Mesh networking · See more »
Minimum degree spanning tree
In graph theory, for a connected graph G, a spanning tree T is a subgraph of G with the least number of edges that still spans G. A number of properties can be proved about T. T is acyclic, has (|V|-1) edges where V is the number of vertices in G etc.
New!!: Spanning tree and Minimum degree spanning tree · See more »
Minimum spanning tree
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted (un)directed graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
New!!: Spanning tree and Minimum spanning tree · See more »
Multigraph
In mathematics, and more specifically in graph theory, a multigraph (in contrast to a simple graph) is a graph which is permitted to have multiple edges (also called parallel edges), that is, edges that have the same end nodes.
New!!: Spanning tree and Multigraph · See more »
Open Shortest Path First
Open Shortest Path First (OSPF) is a routing protocol for Internet Protocol (IP) networks.
New!!: Spanning tree and Open Shortest Path First · See more »
Pathfinding
Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points.
New!!: Spanning tree and Pathfinding · See more »
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
New!!: Spanning tree and Planar graph · See more »
Proofs from THE BOOK
Proofs from THE BOOK is a book of mathematical proofs by Martin Aigner and Günter M. Ziegler.
New!!: Spanning tree and Proofs from THE BOOK · See more »
Queue (abstract data type)
In computer science, a queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue.
New!!: Spanning tree and Queue (abstract data type) · See more »
Random minimum spanning tree
In mathematics, a random minimum spanning tree may be formed by assigning random weights from some distribution to the edges of an undirected graph, and then constructing the minimum spanning tree of the graph.
New!!: Spanning tree and Random minimum spanning tree · See more »
Randomness
Randomness is the lack of pattern or predictability in events.
New!!: Spanning tree and Randomness · See more »
Routing loop problem
A routing loop is a common problem with various types of networks, particularly computer networks.
New!!: Spanning tree and Routing loop problem · See more »
Sharp-P-complete
#P-complete, pronounced "sharp P complete" or "number P complete" is a complexity class in computational complexity theory.
New!!: Spanning tree and Sharp-P-complete · See more »
SIAM Journal on Computing
The SIAM Journal on Computing is a scientific journal focusing on the mathematical and formal aspects of computer science.
New!!: Spanning tree and SIAM Journal on Computing · See more »
Spanning Tree Protocol
The Spanning Tree Protocol (STP) is a network protocol that builds a loop-free logical topology for Ethernet networks.
New!!: Spanning tree and Spanning Tree Protocol · See more »
Springer Science+Business Media
Springer Science+Business Media or Springer, part of Springer Nature since 2015, is a global publishing company that publishes books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.
New!!: Spanning tree and Springer Science+Business Media · See more »
Stack (abstract data type)
In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations.
New!!: Spanning tree and Stack (abstract data type) · See more »
Switching loop
A Switching loop or bridge loop occurs in computer networks when there is more than one Layer 2 (OSI model) path between two endpoints (e.g. multiple connections between two network switches or two ports on the same switch connected to each other).
New!!: Spanning tree and Switching loop · See more »
Symposium on Theory of Computing
The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science.
New!!: Spanning tree and Symposium on Theory of Computing · See more »
Telecommunications network
A telecommunications network is a collection of terminal nodes, links are connected so as to enable telecommunication between the terminals.
New!!: Spanning tree and Telecommunications network · See more »
Time complexity
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
New!!: Spanning tree and Time complexity · See more »
Topological graph theory
In mathematics, topological graph theory is a branch of graph theory.
New!!: Spanning tree and Topological graph theory · See more »
Trémaux tree
In graph theory, a Trémaux tree of an undirected graph G is a spanning tree of G, rooted at one of its vertices, with the property that every two adjacent vertices in G are related to each other as an ancestor and descendant in the tree.
New!!: Spanning tree and Trémaux tree · See more »
Tree (graph theory)
In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path.
New!!: Spanning tree and Tree (graph theory) · See more »
Tutte polynomial
The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial.
New!!: Spanning tree and Tutte polynomial · See more »
Two-dimensional space
Two-dimensional space or bi-dimensional space is a geometric setting in which two values (called parameters) are required to determine the position of an element (i.e., point).
New!!: Spanning tree and Two-dimensional space · See more »
Vertex (graph theory)
In mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices).
New!!: Spanning tree and Vertex (graph theory) · See more »
Xuong tree
In graph theory, a Xuong tree is a spanning tree T of a given graph G with the property that, in the remaining graph G-T, the number of connected components with an odd number of edges is as small as possible.
New!!: Spanning tree and Xuong tree · See more »
Zorn's lemma
Zorn's lemma, also known as the Kuratowski–Zorn lemma, after mathematicians Max Zorn and Kazimierz Kuratowski, is a proposition of set theory that states that a partially ordered set containing upper bounds for every chain (that is, every totally ordered subset) necessarily contains at least one maximal element.
New!!: Spanning tree and Zorn's lemma · See more »
Redirects here:
Fundamental cutset, Fundamental cycle, Spanning Tree, Spanning Tree (mathematics), Spanning forest, Spanning tree (Mathematics), Spanning tree (mathematics), Spanning tree (networks).
References
[1] https://en.wikipedia.org/wiki/Spanning_tree
