1.
Graph theory
–
In mathematics graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, Graphs are one of the prime objects of study in discrete mathematics. Refer to the glossary of graph theory for basic definitions in graph theory, the following are some of the more basic ways of defining graphs and related mathematical structures. To avoid ambiguity, this type of graph may be described precisely as undirected, other senses of graph stem from different conceptions of the edge set. In one more generalized notion, V is a set together with a relation of incidence that associates with each two vertices. In another generalized notion, E is a multiset of unordered pairs of vertices, Many authors call this type of object a multigraph or pseudograph. All of these variants and others are described more fully below, the vertices belonging to an edge are called the ends or end vertices of the edge. A vertex may exist in a graph and not belong to an edge, V and E are usually taken to be finite, and many of the well-known results are not true for infinite graphs because many of the arguments fail in the infinite case. The order of a graph is |V|, its number of vertices, the size of a graph is |E|, its number of edges. The degree or valency of a vertex is the number of edges that connect to it, for an edge, graph theorists usually use the somewhat shorter notation xy. Graphs can be used to model many types of relations and processes in physical, biological, social, Many practical problems can be represented by graphs. Emphasizing their application to real-world systems, the network is sometimes defined to mean a graph in which attributes are associated with the nodes and/or edges. In computer science, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation, etc. For instance, the structure of a website can be represented by a directed graph, in which the vertices represent web pages. A similar approach can be taken to problems in media, travel, biology, computer chip design. The development of algorithms to handle graphs is therefore of major interest in computer science, the transformation of graphs is often formalized and represented by graph rewrite systems. Graph-theoretic methods, in forms, have proven particularly useful in linguistics. Traditionally, syntax and compositional semantics follow tree-based structures, whose power lies in the principle of compositionality

2.
Vertex (graph theory)
–
In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another. The two vertices forming an edge are said to be the endpoints of this edge, and the edge is said to be incident to the vertices, a vertex w is said to be adjacent to another vertex v if the graph contains an edge. The neighborhood of a v is an induced subgraph of the graph. The degree of a vertex, denoted

3.
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. These pairs are known as edges, arcs, or lines for a graph and as arrows, directed edges, directed arcs. The vertices may be part of the structure, or may be external entities represented by integer indices or references. A graph data structure may also associate to each edge some edge value and this data structure allows the storage of additional data on the vertices. Additional data can be stored if edges are stored as objects, in which case each vertex stores its incident edges. Adjacency matrix A two-dimensional matrix, in which the rows represent source vertices, data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices, incidence matrix A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column. The following table gives the time complexity cost of performing operations on graphs, for each of these representations, with |V | the number of vertices. In the matrix representations, the entries encode the cost of following an edge, the cost of edges that are not present are assumed to be ∞. Adjacency lists are generally preferred because they efficiently represent sparse graphs. a, boost Networkx, a Python graph library Graphs Tutorial by Jebril FILALI

4.
Adjacency list
–
In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph and this is one of several commonly used representations of graphs for use in computer programs. An adjacency list representation for a graph associates each vertex in the graph with the collection of its neighboring vertices or edges, an implementation suggested by Guido van Rossum uses a hash table to associate each vertex in a graph with an array of adjacent vertices. In this representation, a vertex may be represented by any hashable object, there is no explicit representation of edges as objects. Cormen et al. suggest an implementation in which the vertices are represented by index numbers and their representation uses an array indexed by vertex number, in which the array cell for each vertex points to a singly linked list of the neighboring vertices of that vertex. The object oriented incidence list structure suggested by Goodrich and Tamassia has special classes of vertex objects, each vertex object has an instance variable pointing to a collection object that lists the neighboring edge objects. In turn, each edge points to the two vertex objects at its endpoints. The main operation performed by the adjacency list data structure is to report a list of the neighbors of a given vertex, using any of the implementations detailed above, this can be performed in constant time per neighbor. In other words, the time to report all of the neighbors of a vertex v is proportional to the degree of v. It is also possible, but not as efficient, to use adjacency lists to test whether an edge exists or does not exist between two specified vertices. If the neighbors are represented as an array, binary search may be used instead. The other significant difference between lists and adjacency matrices is in the efficiency of the operations they perform. In an adjacency list, the neighbors of each vertex may be listed efficiently, in an adjacency matrix, this operation takes time proportional to the number of vertices in the graph, which may be significantly higher than the degree. On the other hand, the adjacency matrix allows testing whether two vertices are adjacent to other in constant time, the adjacency list is slower to support this operation. For use as a structure, the main alternative to the adjacency list is the adjacency matrix. Besides avoiding wasted space, this compactness encourages locality of reference, however, for a sparse graph, adjacency lists require less space, because they do not waste any space to represent edges that are not present. Using a naïve array implementation on a 32-bit computer, an adjacency list for a graph requires about 2| E | = 8| E | bytes of space. Noting that a simple graph can have at most | V |2/2 edges, allowing loops

5.
Adjacency matrix
–
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph, in the special case of a finite simple graph, the adjacency matrix is a -matrix with zeros on its diagonal. If the graph is undirected, the matrix is symmetric. The relationship between a graph and the eigenvalues and eigenvectors of its matrix is studied in spectral graph theory. The adjacency matrix should be distinguished from the matrix for a graph. The diagonal elements of the matrix are all zero, since edges from a vertex to itself are not allowed in simple graphs and it is also sometimes useful in algebraic graph theory to replace the nonzero elements with algebraic variables. Loops may be counted either once or twice, as long as a consistent convention is followed, undirected graphs often use the latter convention of counting loops twice, whereas directed graphs typically use the former convention. In this case, the smaller matrix B uniquely represents the graph, B is sometimes called the biadjacency matrix. Formally, let G = be a graph with parts U = and V =. The biadjacency matrix is the r × s 0–1 matrix B in which bi, j =1 if and only if ∈ E. If G is a multigraph or weighted graph then the elements bi. An -adjacency matrix A of a graph has Ai, j = a if is an edge, b if it is not. The Seidel adjacency matrix is a -adjacency matrix and this matrix is used in studying strongly regular graphs and two-graphs. The distance matrix has in position the distance between vertices vi and vj, the distance is the length of a shortest path connecting the vertices. Unless lengths of edges are explicitly provided, the length of a path is the number of edges in it. The distance matrix resembles a high power of the adjacency matrix, the convention followed here is that each edge adds 1 to the appropriate cell in the matrix, and each loop adds 2. This allows the degree of a vertex to be found by taking the sum of the values in either its respective row or column in the adjacency matrix. In directed graphs, the in-degree of a vertex can be computed by summing the entries of the row

6.
Incidence matrix
–
In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the entry in row x and column y is 1 if x and y are related and 0 if they are not. Incidence matrices are used in graph theory. In graph theory an undirected graph has two kinds of matrices, unoriented and oriented. For example the matrix of the undirected graph shown on the right is a matrix consisting of 4 rows and 4 columns. If we look at the matrix, we see that the sum of each column is equal to 2. This is because each edge has a vertex connected to each end, the oriented incidence matrix of an undirected graph is the incidence matrix, in the sense of directed graphs, of any orientation of the graph. That is, in the column of edge e, there is one 1 in the row corresponding to one vertex of e and one −1 in the row corresponding to the vertex of e. The oriented incidence matrix is unique up to negation of any of the columns, the discrete Laplacian is obtained from the oriented incidence matrix B by the formula B B T. The integral cycle space of a graph is equal to the space of its oriented incidence matrix. The binary cycle space is the space of its oriented or unoriented incidence matrix. The incidence matrix of a graph is a generalization of the oriented incidence matrix. It is the matrix of any bidirected graph that orients the given signed graph. The column of a positive edge has a 1 in the row corresponding to one endpoint, the column of a negative edge has either a 1 or a −1 in both rows. The line graph and Kirchhoff matrix properties generalize to signed graphs, the definitions of incidence matrix apply to graphs with loops and multiple edges. Because the edges of graphs can only have two vertices, the column of an incidence matrix for graphs can only have two non-zero entries. By contrast, a hypergraph can have multiple vertices assigned to one edge, thus, in this case the incidence matrix is also a biadjacency matrix of the Levi graph of the structure. As there is a hypergraph for every Levi graph, and vice versa, an important example is a finite geometry

7.
DOT (graph description language)
–
DOT is a plain text graph description language. DOT graphs are typically files with the file extension gv or dot, the extension gv is preferred to avoid confusion with the extension dot used by early versions of Microsoft Word. Various programs can process DOT files, some, such as OmniGraffle, dot, neato, twopi, circo, fdp, and sfdp, can read a DOT file and render it in graphical form. Others, such as gvpr, gc, acyclic, ccomps, sccmap, finally, others, such as lefty, dotty, and grappa, provide an interactive interface. The GVedit tool combines a text editor with noninteractive image viewer, most programs are part of the Graphviz package or use it internally. At its simplest, DOT can be used to describe an undirected graph, an undirected graph shows simple relations between objects, such as friendship between people. The graph keyword is used to begin a new graph, a double-hyphen is used to show relations between the nodes. Similar to undirected graphs, DOT can describe directed graphs, such as flowcharts, the syntax is the same as for undirected graphs, except the digraph keyword is used to begin the graph, and an arrow is used to show relationships between nodes. Various attributes can be applied to graphs, nodes and edges in DOT files and these attributes can control aspects such as color, shape, and line styles. For nodes and edges, one or more attribute-value pairs are placed in brackets after a statement. Graph attributes are specified as direct attribute-value pairs under the graph element, multiple attributes are separated by a comma or using multiple sets of square brackets. Node attributes are placed after a statement containing only the name of the node, hTML-like labels are only available on versions of Graphviz that are newer than mid-November 2003. In particular, they are not part of release 1.10, dot supports C and C++ style single line and multiple line comments. In addition, it ignores lines with a number sign symbol as their first character, following is an example script that describes the bonding structure of an ethane molecule. This is a graph and contains node attributes as explained above. The DOT language defines a graph, but does not provide facilities for rendering the graph, viz. js - A simple Graphviz JavaScript client Grappa - A partial port of Graphviz to Java. Beluging - A Python & Google Cloud based viewer of DOT, tulip can import dot files for analysis OmniGraffle can import a subset of DOT, producing an editable document. Thus, depending on the used, users must rely on automated layout algorithms or tediously hand-positioned nodes

8.
LCF notation
–
The cycle itself includes two out of the three adjacencies for each vertex, and the LCF notation specifies how far along the cycle each vertexs third neighbor is. A single graph may have different representations in LCF notation. In a Hamiltonian graph, the vertices can be arranged in a cycle, the third edge from each vertex can then be described by how many positions clockwise or counter-clockwise it leads. The basic form of the LCF notation is just the sequence of numbers of positions, starting from an arbitrarily chosen vertex. The numbers between the brackets are interpreted modulo N, where N is the number of vertices, often the pattern repeats, and the number of repetitions can be indicated by a superscript in the notation. For example, the Nauru graph, shown on the right, has four repetitions of the same six offsets, a single graph may have multiple different LCF notations, depending on the choices of Hamiltonian cycle and starting vertex. LCF notation is useful in publishing concise descriptions of Hamiltonian cubic graphs, in addition, some software packages for manipulating graphs include utilities for creating a graph from its LCF notation. If a graph is represented by LCF notation, it is straightforward to test whether the graph is bipartite, a more complex extended version of LCF notation was provided by Coxeter, Frucht, and Powers in later work. The Nauru graph satisfies this condition with 4, and so can be written 4 in the extended notation, math Games, Cubic Symmetric Graphs, Mathematical Association of America Cubic Hamiltonian Graphs from LCF Notation - JavaScript interactive application, built with D3js library

9.
Newick format
–
In mathematics, Newick tree format is a way of representing graph-theoretical trees with edge lengths using parentheses and commas. The adopted format is a generalization of the format developed by Meacham in 1984 for the first tree-drawing programs in Felsensteins PHYLIP package. The following tree, could be represented in Newick format in several ways, no nodes are named, leaf nodes are named F, all nodes are named, all, when an unrooted tree is represented in Newick notation, an arbitrary node is chosen as its root. Whether rooted or unrooted, typically a representation is rooted on an internal node. A rooted binary tree that is rooted on a node has exactly two immediate descendant nodes for each internal node. A binary tree rooted from a leaf has at most one immediate descendant node for the root node, Name, the name of a node Length, the length of a tree edge. Whitespace within string is often prohibited, sometimes the Name string must be of a specified fixed length, otherwise the punctuation characters from the grammar are prohibited. The Tree --> Branch, production makes the entire tree descendant from nowhere, which can be nonsensical, generally, a root node labeled as Internal should be construed as a leaf if and only if it has exactly one Branch in its BranchSet. The second RootLeaf production is for rooting a tree one of its two or more leaves. PhyloXML T-REX allows handling phylogenetic trees and networks in the Newick format, gary Olsens Interpretation of the Newicks 8,45 Tree Format Standard Miyamoto and Goodmans Phylogram of Eutherian Mammals An example of a large phylogram with its Newick format representation

10.
Graph database
–
In computing, a graph database is a database that uses graph structures for semantic queries with nodes, edges and properties to represent and store data. A key concept of the system is the graph, which directly relates data items in the store, the relationships allow data in the store to be linked together directly, and in many cases retrieved with one operation. Graph databases, by design, allow simple and fast retrieval of complex structures that are difficult to model in relational systems. The underlying storage mechanism of graph databases can vary, some depend on a relational engine and store the graph data in a table. Others use a store or document-oriented database for storage, making them inherently NoSQL structures. Most graph databases based on non-relational storage engines also add the concept of tags or properties and this allows data elements to be categorized for easy retrieval en masse. Retrieving data from a graph database requires a language other than SQL. Some standardization efforts have occurred, leading to multi-vendor query languages like Gremlin, SPARQL, in addition to having query language interfaces, some graph databases are accessed through application programming interfaces. Graph databases are based on theory, and employ nodes, edges. Nodes represent entities such as people, businesses, accounts, or any item to be tracked. They are roughly the equivalent of the record, relation, or row in a relational database, edges, also termed graphs or relationships, are the lines that connect nodes to other nodes, they represent the relationship between them. Meaningful patterns emerge when examining the connections and interconnections of nodes, properties, edges are the key concept in graph databases, representing an abstraction that is not directly implemented in other systems. Properties are germane information that relate to nodes, the relational model gathers data together using information in the data. For example, one might look for all the users phone number contains the area code 311. This would be done by searching selected datastores, or tables, generally, the tables are physically stored so that lookups on these keys are fast. Relational databases do not inherently contain the idea of fixed relationships between records, instead, related data is linked to each other by storing one records unique key in another records data. For example, a table containing email addresses for users might hold a data item called userpk and this operation, termed a join, can be computationally costly. In contrast, graph databases directly store the relationships between records, instead of an email address being found by looking up its users key in the userpk column, the user record has a pointer directly to the email address record

11.
Graph drawing
–
A drawing of a graph or network diagram is a pictorial representation of the vertices and edges of a graph. This drawing should not be confused with the graph itself, very different layouts can correspond to the same graph, in the abstract, all that matters is which pairs of vertices are connected by edges. In the concrete, however, the arrangement of vertices and edges within a drawing affects its understandability, usability, fabrication cost. The problem gets worse, if the changes over time by adding and deleting edges. Upward planar drawing uses the convention that every edge is oriented from a vertex to a higher vertex. Many different quality measures have been defined for graph drawings, in an attempt to find means of evaluating their aesthetics. In addition to guiding the choice between different layout methods for the graph, some layout methods attempt to directly optimize these measures. The crossing number of a drawing is the number of pairs of edges cross each other. If the graph is planar, then it is convenient to draw it without any edge intersections, that is, in this case. However, nonplanar graphs frequently arise in applications, so graph drawing algorithms must generally allow for edge crossings, the area of a drawing is the size of its smallest bounding box, relative to the closest distance between any two vertices. Drawings with smaller area are generally preferable to those with area, because they allow the features of the drawing to be shown at greater size. The aspect ratio of the box may also be important. Symmetry display is the problem of finding symmetry groups within a given graph, some layout methods automatically lead to symmetric drawings, alternatively, some drawing methods start by finding symmetries in the input graph and using them to construct a drawing. It is important that edges have shapes that are as simple as possible, in polyline drawings, the complexity of an edge may be measured by its number of bends, and many methods aim to provide drawings with few total bends or few bends per edge. Similarly for spline curves the complexity of an edge may be measured by the number of points on the edge. Several commonly used quality measures concern lengths of edges, it is desirable to minimize the total length of the edges as well as the maximum length of any edge. Additionally, it may be preferable for the lengths of edges to be rather than highly varied. Angular resolution is a measure of the sharpest angles in a graph drawing, if a graph has vertices with high degree then it necessarily will have small angular resolution, but the angular resolution can be bounded below by a function of the degree

12.
Linked data
–
In computing, linked data is a method of publishing structured data so that it can be interlinked and become more useful through semantic queries. This enables data from different sources to be connected and queried, tim Berners-Lee, director of the World Wide Web Consortium, coined the term in a 2006 design note about the Semantic Web project. Tim Berners-Lee outlined four principles of linked data in his Linked Data note of 2006, paraphrased along the following lines, Use HTTP URIs so that these things can be looked up. Provide useful information about what a name identifies when its looked up, using standards such as RDF, SPARQL. Refer to other things using their HTTP URI-based names when publishing data on the Web, tim Berners-Lee gave a presentation on linked data at the TED2009 conference. In it, he restated the linked data principles as three extremely simple rules, All kinds of things, they have names now that start with HTTP. If I take one of these HTTP names and I look it up. I will get back some data in a format which is kind of useful data that somebody might like to know about that thing. When I get back that information its not just got somebodys height and weight, and when it has relationships, whenever it expresses a relationship then the other thing that its related to is given one of those names that starts with HTTP. Tim Berners-Lee gives the clearest definition of linked data in differentiation with linked data. Linked Open Data is Linked Data which is released under an open licence, large linked open data sets include DBpedia and Freebase. The term linked open data has been in use since at least February 2007, the mailing list was initially hosted by the SIMILE project at the Massachusetts Institute of Technology. In October 2007, datasets consisted of two billion RDF triples, which were interlinked by over two million RDF links. By September 2011 this had grown to 31 billion RDF triples, a detailed statistical breakdown was published in 2014. There are a number of European Union projects involving linked data and these include the linked open data around the clock project, the PlanetData project, the DaPaaS project, and the Linked Open Data 2 project. Data linking is one of the goals of the EU Open Data Portal. DBpedia – a dataset containing extracted data from Wikipedia, it contains about 3