Graphs and NetworksIntroduction

A graph is a collection of vertices connected by edges.","link":"/course/graph-theory/introduction"},"directed-graph":{"title":"Directed Graph","text":"

In a directed graph, every edge has an “arrow”, i.e. a start vertex and an end vertex.","link":"/course/graph-theory/introduction#intro-1"},"subgraph":{"title":"Subgraph","text":"

A graph is a subgraph of another graph, if it is formed by a subset of the larger graphs edges and vertices.","link":"/course/graph-theory/introduction#intro-2"},"graph-order":{"title":"Order","text":"

The order of a graph is the number of vertices in it.","link":"/course/graph-theory/introduction#intro-3"},"graph-degree":{"title":"Degree","text":"

The degree of a vertex is the number of edges that meet at that vertex.","link":"/course/graph-theory/introduction#intro-3"},"graph-cycle":{"title":"Cycle","text":"

Cycles are graphs that consist of a single loop of vertices.","link":"/course/graph-theory/introduction#intro-4"},"complete-graph":{"title":"Complete graph","text":"

In complete graphs, every vertex is connected to every other vertex. A complete graph with n vertices has n×n−12 edges.","link":"/course/graph-theory/handshakes#handshakes-3"},"bipartite-graph":{"title":"Bipartite graph","text":"

A (complete) bipartite graph consists of two sets of vertices. Every vertex is connected to all the vertices in the opposite set, but none of the vertices in its own set.","link":"/course/graph-theory/handshakes#handshakes-4"},"subdivision":{"title":"Subdivisions","text":"

To create a subdivision of a graph you add additional vertices along its edges."},"proof":{"title":"Proof","text":"

A proof is a logical argument that shows beyond any doubt that a certain statement is true."},"polyhedron":{"title":"Polyhedron","text":"

A polyhedron (the plural is polyhedra) is a three-dimensional solid with no curved surfaces or edges. All faces of a polyhedron are polygons. For example, a cube and a pyramid are polyhedra, but a sphere is not.","link":"/course/polyhedra/polyhedra"},"polygon":{"title":"Polygon","text":"

A polygon is geometric shape that is made up of straight line segments. Polygons cannot contain any curved sides, or holes. For example, a square is a polygon but a circle is not.","image":"polygon.svg","link":"/course/polyhedra/polygons#polygons"},"dna":{"title":"DNA","text":"

DNA (deoxyribonucleic acid) is a molecule that contains the genetic blueprint of all living organisms. Most DNAs consist of two strands forming a double helix. Genetic information is encoded in the order of four nucleic acids (A, G, C and T) which make up the DNA. DNA sequencing is the process of extracting this information – an essential technique in biology, medicine, genetics and biotechnology."},"np":{"title":"NP hard problems","text":"

Computational complexity theory is about determining how “difficult” problems are to be solved by a computer. NP hard (non-deterministic polynomial-time hard) is the class of the most difficult problems."},"millennium-prize":{"title":"Millennium prize problems","text":"

The seven Millennium prize problems are some of the most difficult open problems in Mathematics. They were listed in 2000 by the Clay Mathematics Institute, and each hold a $1m reward:

• P vs NP
• The Hodge conjecture
• The Poincaré conjecture
• The Riemann hypothesis
• Yang-Mills existence and mass gap
• Navier-Stokes existence and smoothness
• The Birch and Swinnerton-Dyer conjecture

  So far, just one of the problems, the Poincaré conjecture, has been solved. However the mathematician who solved it, Grigori Perelman, declined the award."}}