Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Download
Faster access than browser!
 

Graph (discrete mathematics)

Index 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". [1]

83 relations: Biased graph, Binary relation, Bipartite graph, Cardinal number, Cartesian product of graphs, Category (mathematics), Category theory, Cayley graph, Chordal graph, Cograph, Comma category, Complement graph, Complete bipartite graph, Computational biology, Computer science, Conceptual graph, CRC Press, Diagram, Discrete mathematics, Disjoint union of graphs, Distance-regular graph, Distance-transitive graph, Dover Publications, Dual graph, Edge contraction, Element (mathematics), Finite set, Finite-state machine, Functor, Geographic information system, Geometric networks, Glossary of graph theory terms, Graph (abstract data type), Graph automorphism, Graph coloring, Graph database, Graph drawing, Graph homomorphism, Graph rewriting, Graph theory, Graphon, Hypergraph, James Joseph Sylvester, K-edge-connected graph, K-vertex-connected graph, Lexicographic product of graphs, Line graph, List of graph theory topics, Loop (graph theory), Mathematical structure, ..., Mathematics, Matroid, Model theory, Morphism, Multigraph, Multiple edges, Multiset, Network theory, Null graph, Ordered pair, Orientation (graph theory), Partition of a set, Path (graph theory), Perfect graph, Petersen graph, Power graph analysis, Schreier coset graph, Series-parallel graph, Set (mathematics), Shortest path problem, Signed graph, Simplex, Simplicial complex, Strong product of graphs, Strongly regular graph, Structure (mathematical logic), Symmetric graph, Tensor product of graphs, Travelling salesman problem, Twitter, Vertex (graph theory), Vertex-transitive graph, Weighted correlation network analysis. Expand index (33 more) »

Biased graph

In mathematics, a biased graph is a graph with a list of distinguished circles (edge sets of simple cycles), such that if two circles in the list are contained in a theta graph, then the third circle of the theta graph is also in the list.

New!!: Graph (discrete mathematics) and Biased graph · See more »

Binary relation

In mathematics, a binary relation on a set A is a set of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2.

New!!: Graph (discrete mathematics) and Binary relation · See more »

Bipartite graph

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph.

New!!: Graph (discrete mathematics) and Bipartite graph · See more »

Cardinal number

In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets.

New!!: Graph (discrete mathematics) and Cardinal number · See more »

Cartesian product of graphs

In graph theory, the Cartesian product G \square H of graphs G and H is a graph such that.

New!!: Graph (discrete mathematics) and Cartesian product of graphs · See more »

Category (mathematics)

In mathematics, a category (sometimes called an abstract category to distinguish it from a concrete category) is an algebraic structure similar to a group but without requiring inverse or closure properties.

New!!: Graph (discrete mathematics) and Category (mathematics) · See more »

Category theory

Category theory formalizes mathematical structure and its concepts in terms of a labeled directed graph called a category, whose nodes are called objects, and whose labelled directed edges are called arrows (or morphisms).

New!!: Graph (discrete mathematics) and Category theory · See more »

Cayley graph

In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group.

New!!: Graph (discrete mathematics) and Cayley graph · See more »

Chordal graph

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle.

New!!: Graph (discrete mathematics) and Chordal graph · See more »

Cograph

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union.

New!!: Graph (discrete mathematics) and Cograph · See more »

Comma category

In mathematics, a comma category (a special case being a slice category) is a construction in category theory.

New!!: Graph (discrete mathematics) and Comma category · See more »

Complement graph

In graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in.

New!!: Graph (discrete mathematics) and Complement graph · See more »

Complete bipartite graph

No description.

New!!: Graph (discrete mathematics) and Complete bipartite graph · See more »

Computational biology

Computational biology involves the development and application of data-analytical and theoretical methods, mathematical modeling and computational simulation techniques to the study of biological, behavioral, and social systems.

New!!: Graph (discrete mathematics) and Computational biology · See more »

Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

New!!: Graph (discrete mathematics) and Computer science · See more »

Conceptual graph

Conceptual graphs (CGs) are a formalism for knowledge representation.

New!!: Graph (discrete mathematics) and Conceptual graph · See more »

CRC Press

The CRC Press, LLC is a publishing group based in the United States that specializes in producing technical books.

New!!: Graph (discrete mathematics) and CRC Press · See more »

Diagram

A diagram is a symbolic representation of information according to some visualization technique.

New!!: Graph (discrete mathematics) and Diagram · See more »

Discrete mathematics

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

New!!: Graph (discrete mathematics) and Discrete mathematics · See more »

Disjoint union of graphs

In graph theory, a branch of mathematics, the disjoint union of graphs is an operation that combines two or more graphs to form a larger graph.

New!!: Graph (discrete mathematics) and Disjoint union of graphs · See more »

Distance-regular graph

In mathematics, a distance-regular graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k, and i.

New!!: Graph (discrete mathematics) and Distance-regular graph · See more »

Distance-transitive graph

In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance, there is an automorphism of the graph that carries v to x and w to y.

New!!: Graph (discrete mathematics) and Distance-transitive graph · See more »

Dover Publications

Dover Publications, also known as Dover Books, is an American book publisher founded in 1941 by Hayward Cirker and his wife, Blanche.

New!!: Graph (discrete mathematics) and Dover Publications · See more »

Dual graph

In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of.

New!!: Graph (discrete mathematics) and Dual graph · 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!!: Graph (discrete mathematics) and Edge contraction · See more »

Element (mathematics)

In mathematics, an element, or member, of a set is any one of the distinct objects that make up that set.

New!!: Graph (discrete mathematics) and Element (mathematics) · See more »

Finite set

In mathematics, a finite set is a set that has a finite number of elements.

New!!: Graph (discrete mathematics) and Finite set · See more »

Finite-state machine

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation.

New!!: Graph (discrete mathematics) and Finite-state machine · See more »

Functor

In mathematics, a functor is a map between categories.

New!!: Graph (discrete mathematics) and Functor · See more »

Geographic information system

A geographic information system (GIS) is a system designed to capture, store, manipulate, analyze, manage, and present spatial or geographic data.

New!!: Graph (discrete mathematics) and Geographic information system · See more »

Geometric networks

A geometric network is an object commonly used in geographic information systems to model a series of interconnected features.

New!!: Graph (discrete mathematics) and Geometric networks · See more »

Glossary of graph theory terms

This is a glossary of graph theory terms.

New!!: Graph (discrete mathematics) and Glossary of graph theory terms · See more »

Graph (abstract data type)

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics, specifically the field of graph theory.

New!!: Graph (discrete mathematics) and Graph (abstract data type) · See more »

Graph automorphism

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.

New!!: Graph (discrete mathematics) and Graph automorphism · See more »

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.

New!!: Graph (discrete mathematics) and Graph coloring · See more »

Graph database

In computing, a graph database (GDB) is a database that uses graph structures for semantic queries with nodes, edges and properties to represent and store data.

New!!: Graph (discrete mathematics) and Graph database · See more »

Graph drawing

Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, linguistics, and bioinformatics.

New!!: Graph (discrete mathematics) and Graph drawing · See more »

Graph homomorphism

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure.

New!!: Graph (discrete mathematics) and Graph homomorphism · See more »

Graph rewriting

In computer science, graph transformation, or graph rewriting, concerns the technique of creating a new graph out of an original graph algorithmically.

New!!: Graph (discrete mathematics) and Graph rewriting · 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!!: Graph (discrete mathematics) and Graph theory · See more »

Graphon

In graph theory and statistics, a graphon is a symmetric measurable function W:^2\to, that is important in the study of dense graphs.

New!!: Graph (discrete mathematics) and Graphon · See more »

Hypergraph

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices.

New!!: Graph (discrete mathematics) and Hypergraph · See more »

James Joseph Sylvester

James Joseph Sylvester FRS (3 September 1814 – 15 March 1897) was an English mathematician.

New!!: Graph (discrete mathematics) and James Joseph Sylvester · See more »

K-edge-connected graph

In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

New!!: Graph (discrete mathematics) and K-edge-connected graph · See more »

K-vertex-connected graph

In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed.

New!!: Graph (discrete mathematics) and K-vertex-connected graph · See more »

Lexicographic product of graphs

In graph theory, the lexicographic product or graph composition of graphs and is a graph such that.

New!!: Graph (discrete mathematics) and Lexicographic product of graphs · See more »

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name line graph comes from a paper by although both and used the construction before this.

New!!: Graph (discrete mathematics) and Line graph · See more »

List of graph theory topics

This is a list of graph theory topics, by Wikipedia page.

New!!: Graph (discrete mathematics) and List of graph theory topics · See more »

Loop (graph theory)

In graph theory, a loop (also called a self-loop or a "buckle") is an edge that connects a vertex to itself.

New!!: Graph (discrete mathematics) and Loop (graph theory) · See more »

Mathematical structure

In mathematics, a structure on a set is an additional mathematical object that, in some manner, attaches (or relates) to that set to endow it with some additional meaning or significance.

New!!: Graph (discrete mathematics) and Mathematical structure · 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!!: Graph (discrete mathematics) and 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!!: Graph (discrete mathematics) and Matroid · See more »

Model theory

In mathematics, model theory is the study of classes of mathematical structures (e.g. groups, fields, graphs, universes of set theory) from the perspective of mathematical logic.

New!!: Graph (discrete mathematics) and Model theory · See more »

Morphism

In mathematics, a morphism is a structure-preserving map from one mathematical structure to another one of the same type.

New!!: Graph (discrete mathematics) and Morphism · 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!!: Graph (discrete mathematics) and Multigraph · See more »

Multiple edges

In graph theory, multiple edges (also called parallel edges or a multi-edge), are two or more edges that are incident to the same two vertices.

New!!: Graph (discrete mathematics) and Multiple edges · See more »

Multiset

In mathematics, a multiset (aka bag or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements.

New!!: Graph (discrete mathematics) and Multiset · See more »

Network theory

Network theory is the study of graphs as a representation of either symmetric relations or asymmetric relations between discrete objects.

New!!: Graph (discrete mathematics) and Network theory · See more »

Null graph

In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").

New!!: Graph (discrete mathematics) and Null graph · See more »

Ordered pair

In mathematics, an ordered pair (a, b) is a pair of objects.

New!!: Graph (discrete mathematics) and Ordered pair · See more »

Orientation (graph theory)

In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph.

New!!: Graph (discrete mathematics) and Orientation (graph theory) · See more »

Partition of a set

In mathematics, a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets.

New!!: Graph (discrete mathematics) and Partition of a set · See more »

Path (graph theory)

In graph theory, a path in a graph is a finite or infinite sequence of edges which connect a sequence of vertices which, by most definitions, are all distinct from one another.

New!!: Graph (discrete mathematics) and Path (graph theory) · See more »

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph.

New!!: Graph (discrete mathematics) and Perfect graph · See more »

Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges.

New!!: Graph (discrete mathematics) and Petersen graph · See more »

Power graph analysis

In computational biology, power graph analysis is a method for the analysis and representation of complex networks.

New!!: Graph (discrete mathematics) and Power graph analysis · See more »

Schreier coset graph

In the area of mathematics called combinatorial group theory, the Schreier coset graph is a graph associated to a group G, a generating set, and a subgroup H ≤ G. The graph is named after Otto Schreier, who used the term “Nebengruppenbild”.

New!!: Graph (discrete mathematics) and Schreier coset graph · See more »

Series-parallel graph

In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations.

New!!: Graph (discrete mathematics) and Series-parallel graph · See more »

Set (mathematics)

In mathematics, a set is a collection of distinct objects, considered as an object in its own right.

New!!: Graph (discrete mathematics) and Set (mathematics) · See more »

Shortest path problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

New!!: Graph (discrete mathematics) and Shortest path problem · See more »

Signed graph

In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign.

New!!: Graph (discrete mathematics) and Signed graph · See more »

Simplex

In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions.

New!!: Graph (discrete mathematics) and Simplex · See more »

Simplicial complex

In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their ''n''-dimensional counterparts (see illustration).

New!!: Graph (discrete mathematics) and Simplicial complex · See more »

Strong product of graphs

In graph theory, the strong product G ⊠ H of graphs G and H is a graph such that.

New!!: Graph (discrete mathematics) and Strong product of graphs · See more »

Strongly regular graph

In graph theory, a strongly regular graph is defined as follows.

New!!: Graph (discrete mathematics) and Strongly regular graph · See more »

Structure (mathematical logic)

In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it.

New!!: Graph (discrete mathematics) and Structure (mathematical logic) · See more »

Symmetric graph

In the mathematical field of graph theory, a graph G is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphism such that In other words, a graph is symmetric if its automorphism group acts transitively upon ordered pairs of adjacent vertices (that is, upon edges considered as having a direction).

New!!: Graph (discrete mathematics) and Symmetric graph · See more »

Tensor product of graphs

In graph theory, the tensor product G × H of graphs G and H is a graph such that.

New!!: Graph (discrete mathematics) and Tensor product of graphs · See more »

Travelling salesman problem

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

New!!: Graph (discrete mathematics) and Travelling salesman problem · See more »

Twitter

Twitter is an online news and social networking service on which users post and interact with messages known as "tweets".

New!!: Graph (discrete mathematics) and Twitter · 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!!: Graph (discrete mathematics) and Vertex (graph theory) · See more »

Vertex-transitive graph

In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphism such that In other words, a graph is vertex-transitive if its automorphism group acts transitively upon its vertices.

New!!: Graph (discrete mathematics) and Vertex-transitive graph · See more »

Weighted correlation network analysis

Weighted correlation network analysis, also known as weighted gene co-expression network analysis (WGCNA), is a widely used data mining method especially for studying biological networks based on pairwise correlations between variables.

New!!: Graph (discrete mathematics) and Weighted correlation network analysis · See more »

Redirects here:

Adjacency relation, Edge(graph theory), Edge-weighted graph, Finite graph, Finite undirected graph, Graph (graph theory), Graph (network), Graph node, Incident (graph theory), Multiple edge(graph theory), Non-adjacent, Order (graph theory), Points and lines, Simple graph, Size (graph theory), Trivial graph, Undirected, Undirected (graph theory), Undirected graph.

References

[1] https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)

OutgoingIncoming
Hey! We are on Facebook now! »