What is Graph theory: Definition and 174 Discussions
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 (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.
I have a unique problem and looking for a known fast algorithm for it. I have an unweighted but directed graph `G`. I then have a subset collection of nodes `S` existing in `G`. I want to find the minimum sub tree in `G` such that it contains all the nodes in `S`.
I so far found Chu-Liu/Edmonds...
Hi,
I've a question related to the graph theory.
Take a connected graph with ##n## nodes and ##b## edges. We know there are ##m = b - n + 1## fundamental circuits.
Which is the total number of nonempty circuits or edge-disjoint unions of circuits ? If we do not take in account the circuit...
I know that if an undirected graph is a tree then its number of edges satisfies ## |E| = |V| - 1 ##.
If a directed graph ( digraph ) is a tree, is the result also true? ( I can imagine just taking an undirected tree and making its edges directed but this is specious since it's a little bit more...
Hi,
I was reading through some slides about graph clustering. In the slides was a very short discussion about 'eigenvectors and segmentation'. I don't quite understand where one of the formulae comes from.
Context: We have some undirected graph with an affinity matrix (i.e. weighted adjacency...
Hello everybody!
I have to implement a sudoku solver in C ++ taking advantage by graph coloring theory, where each number to insert is a color of the associated graph node. In particular I would like to use the Welsh-Powell algorithm.
I find myself in trouble starting with this project and I...
Attempt - I am stuck at this problem for hours, couldn't make any progress. Still, here's what I've done :
Let ## e_1 \in E_1 \setminus E_2 ## be arbitrary. Suppose for the sake of contradiction that ## \forall ## ## e_2 \in E_2 \setminus E_1 ##, ## T_1' = \langle V,(E_1\setminus \{ e_1 \})...
Hello everybody,
I hope it is the right section to post.
For an exam, I should delve into a topic concerning graph theory. My work should include theoretical explanation, pseudo code, correctness analysis, complexity analysis and code implementation (C ++, python or other).
Could someone...
We are working on an architectural project using graphs and we are looking for a way to combine separate graphs into one. We looked into methods to generate graph homorphisms, following the maximum graph homomorphism (MGH) (Langberg et al. 2006) and Paweł Rzążewski’s Exact Algorithm (2014)...
Hi,
I read a book on graph theory by West and is interested to learn algorithmic graph theory now.What algorithms are important in algorithmic graph theory in all fields such as planarity detection,1-factor ,hamiltonian cycle detection,finding eulerian tour,greedy coloring,graph realization
Given a minimal non-planar graph G, we need to find out if G', which is G-e, where e is a removed edge, we need to prove that there exists an edge e such that its removal would make G' a maximal planar graph.
My idea in trying to figure this out would be by taking a minimal non-planar graph and...
Our problem involves a graph G that is simple and connected, where every biconnected component is a cycle that has at least four vertices in it. The maximum number of components we can get from removing a cut vertex is 4, and we are asked to find tight bounds on the chromatic number of G.
My...
The problem is for us to consider a biconnected decomposition, and that proof for a graph, the degrees of all the vertices in a graph is even iff the degrees of all the vertices in all of its maximal biconnected components is even
For solving that if the degrees of all the vertices in the...
Hi,
I am very new in Graph Theory, and am currently trying to figure out it's potential to solve my research problem. Here it goes:
I have a large physical network (10000 nodes, around 14,000 edges), it can be represented by an undirected weighted graph. Many portions of the network might have...
In order to try and sovle this problem, my idea here was to use an extremal argument, with two equal length maximum paths on a tree. I said that no matter where the two graphs started, they'd end up having to cross paths since if there were two distinct paths with equal lengths the graph would...
For my base case I just used a graph with three vertices and 2 edges. Decomposing this would just give us the same graph, which has a path length of 2.
The inductive step is where I'm having some trouble: One idea I have is that we take a graph G then inductively remove an edge to create two...
My Problem: Given a Graph G = (V,E), where the number of vertices is less than or equal to the number of edges, use induction to prove that the graph contains at least one cycle (the graph is not required to be completely connected).
My attempt: For my base case, I used only one vertex with one...
Hello, recently I was looking into visiting Tokyo and started looking into its complicated but wonderfully efficient railway system. I picked 6 destinations in the area and looked up how much it would cost to go from anyone of the locations to any other.
Then I started to wonder, if I...
Prove that if a simple graph G has 6 vertices then G or its complement has a subgraph isomorphic to ##K_3##.
The proof begins by noting that is must be the case that G or its complement as a vertex with degree at least 3. Why is this the case?
I have a problem understanding a definition at page 93 of 'from perturbative to constructive renormalization', that is related to Graph Theory, and he uses it on the proof of the uniform BPH theorem for \phi_4^4 (\lambda \phi^4 in D=4).
You have a graph G, a forest of quadrupeds F, and g a...
Homework Statement
Homework Equations
Reduce the matrix to reduced matrix by removing 1 row completely
Number of trees = determinant of [ Ar times ArT ]
The Attempt at a Solution
I removed 4th row to get Ar(reduced matrix)
Then I did Ar times Ar (transpose)
And found it's determinant but I...
Why should a person prefer irrational coordinate system over rational? My friend stated that its because most lines such as ##y=e## cannot be plotted on a rational grid system. But that cannot be true since ##e## does have a rational number summation ##2+1/10+7/100...## which can be utilised to...
Eugene Wigner once famously talked about the "unreasonable effectiveness of mathematics" in describing the natural world. Today again we are seeing this in action in particular with regard to the description of the biological brain from the perspective of neuroscience. Researchers from the Blue...
I'm playing around with Spectral Bisections and Fiedler vectors as ways of bisecting a graph using the sparsest cut. However, I'm finding that even the most trivially simple graphs are bisected incorrectly by this approach. What am I missing?
Take for example a graph that is just a 4x4...
I need recommendations on literature to read. Basically i do not understand these section of Frank Harary's book on graph theory since the definition of what a boundary and a cycle vector is not clearly defined. I have googled literature on it but I am having a tough time finding the right...
I have been long interested in how one might find all of the 240 unique solutions to the SOMA cube puzzle since receiving one for Christmas in 1968. If one were to find all of the solutions (many of them are "similar" and there is an interesting variety "similar" to boot) . . how best to...
Hi!
I'm struggling with these two problems:
1. If for whichever two vertices a and b in the graph G there is only one simple path from a to b, then the graph is a tree.
Eh... isn't this part of the definition for a tree? I really don't even know where to start with proving this statements...
Homework Statement
hello, I have this graph and i have to figure out these so to speak characteristics.
1) find incidence matrix
2) arrange peak according to rank and layers
3)draw new arranged graph
4) find new connection matricies of peaks and arcs
Homework EquationsThe Attempt at a...
Homework Statement
I am trying to verify this theorem for myself.
Theorem: Every graph G containing a cycle satisfies g(G)≤2diam(G)+1
Homework Equations
N/A
The Attempt at a Solution
i have drawn graphs and i failed to verify the theorem. is it even possible, since increasing the girth...
Proof: Let C be a shortest cycle in G. If g(G)>= 2diam(G) + 2, then C has two vertices whose distance in C is at least diam(G)+1.
Question: why is it at least diam(G)+1?
cont. of proof: In G, these vertices have a lesser distance; any shortest path P between them is therefore not a subgraph of...
Hi all,
I am struggling the question, please see attachments.
Thanks a lot
Devise an algorithm which, given a (directed) friendship graph (in the xkcd format), finds the optimal seating arrangement. Your algorithm should include the following:
a description of the required input format...
Hello all,
I recently starting studying graph theory in my free time and have become very interested in the Reconstruction Conjecture. Since I am new on the subject I am not sure where to start my search for additional information/insights/papers on the topic, I thought I would ask here for...
Homework Statement
Given the representation of directed unweighted graph:
typedef struct
{
int n;//num. of vertices
void *info[MAX];//information of vertices
int am[MAX][MAX];//adjacency matrix
}GRAPH;
Write a function int minDegree(GRAPH*); and int maxDegree(GRAPH*); that return the...
I have read in many places that one necessary condition for the existence of a Euler circuit in a directed graph is as follows.
Theorem: "A directed graph has an eulerian circuit if and only if it is connected and each vertex has the same in-degree as out-degree."
However, I don't understand...
Homework Statement
The problem is attached. I don't get this part. Let G = Sn be the group of all permutations of S. S is a set, so how can we permute something in a set?. Neither I know if the 4 power in the S is a typo.
Homework EquationsThe Attempt at a Solution
Homework Statement
The problem is attached and it's part A. There is no need to put problem 4 hence the problem is fully explained in the file attached
Homework Equations
Zk is mod k basically.
The Attempt at a Solution
I know that we have to prove that the transformation is onto,one to one...
Homework Statement
You are given some undirected graph G = (V, E), along with a set S which consists of 0 or more pairs of G's edges.
As an example, a complete graph on 3 vertices (a triangle, basically) would be described as follows: G = (V, E) = ({v1, v2, v3}, {v1v2, v2v3, v1v3}). A set S...
Homework Statement
Take a standard deck of cards, and deal them out into 13 piles of 4 cards each. Then, using the marriage theorem, we can show that it is always possible to select exactly 1 card from each pile, such that the 13 selected cards contain exactly one card of each rank (Ace, 2, 3...
Hi,
In the paper "A triangle-free circle graph with chromatic number 5" from A.A. Ageev, I don't understand what the author mean with the following definition:
Somebody can explain it to me? (I'm not mathematician).
Thanks !
Link to the whole paper...
Homework Statement
1. How many vertices will the following graphs have if they contain:
(a) 12 edges and all vertices of degree 3.
(b) 21 edges, three vertices of degree 4, and the other vertices of degree 3.
(c) 24 edges and all vertices of the same degree.
Homework Equations
"Theorem 1
In...
Homework Statement
I can't understand this paper. I understand the whole incidence matrix stuff, but I don't quiet get how it relates to the linear algebra. I don't know if this is allowed to do, but I will ask you questions line by line, so basically you will read the paper with me explaining...
Homework Statement
A. Show that n^n−2/n! < T(n) by looking at how the symmetric group Sn acts on labelled trees. Use |Sn| = n!
T(n) is the number of unlabeled trees on n vertices
Homework EquationsThe Attempt at a Solution
I can't find any mathematical relation between labelled trees and...
Homework Statement
Exercise 0.1. Suppose that G is a finite graph all of whose vertices has degree two or greater. Prove that a cycle passes through each vertex. Conclude that G cannot be a tree.
Homework EquationsThe Attempt at a Solution
If every vertex in a graph G has degree two or...
Homework Statement
Let G be a connected graph. We say that G is minimally connected if the removal of any edge of G (without deleting any vertices) results in a disconnected graph. (a) Show that a connected, minimally connected graph has no cycles. (b) Show that a connected graph with no cycles...
Homework Statement
Prove that a complete graph with n vertices contains n(n − 1)/2 edges.
Homework EquationsThe Attempt at a Solution
The solution gives and inductive proof, but I am just wondering if this works as well.
If we have a set of n vertices or points and we try to match all...
Homework Statement
1. Prove or disprove up to isomorphism, there is only one 2-regular graph on 5 vertices.
Homework EquationsThe Attempt at a Solution
I am making this thread again hence I think I will get more help in this section
old thread...