I'm learning graphs these days and need to clear few doubts-

  1. Can I determine weather 5 points in two dimensions whose X and Y coordinates are given lie on the same straight line in O(1).
  2. What is the efficient way to find out the degree of the specified vertex in an undirected graph (V,E)? I'm thinking of O(|E|)?
  3. What is the efficient way to find degrees of all vertices in an undirected graph (V,E)? I'm think of O(|V||E|)
  4. if |E| ≥ |V| can I say grapgh will be have guaranteed Euler circuit?
  5. Is it possible to find slope of a straight line in O(1)time given the X and Y coordinates of n points on the line?
  • 1
    $\begingroup$ Sorry but these are five completely separate questions, and they need to be asked as separate questions. I guess you were just trying to be efficient but the problem with putting a bunch of unrelated questions in the same post is that the answers get all jumbled up, which makes it hard for later users to find the answers. $\endgroup$ Commented Dec 19, 2018 at 20:52

2 Answers 2

  1. Yes, anything that has constant input could be done in $O(1)$. Howether if the coordinates have size more than $O(1)$ than you will not be able to even read them in time.
  2. That depends on your representation of the graph and what operations do you count. If you assume that you read the whole graph in some way and then find the needed degree, the complexity will be $O(|V| + |E|)$ if your representation is an edge list, $O(|V|^2)$ if it is an adjacency matrix. If you assume that you already have some representation of the graph in memory you can find the degree in $O(|V|)$ if you have the adjacency matrix.
  3. You can do it in $O(|V| + |E|)$, start with an empty graph (all the degrees are zero) and add the edges one by one. When you add an edge to the graph only two vertices change their degrees.
  4. No, consider the graph $K_4$ (complete graph on $4$ vertices). All the degrees in it are odd so it does not have even en Euler path.
  5. If you want to read the coordinates it takes $O(n)$ operations, so no.
  • $\begingroup$ for second O(|E|) is completely wrong approach? $\endgroup$
    – June
    Commented Dec 18, 2018 at 16:23

Just adding to what @Artur said: You only need 2 points to find the slope of a straight line, even if you're given more, so that's O(1) for me...

  • $\begingroup$ what about read operations for n given points? $\endgroup$
    – June
    Commented Dec 18, 2018 at 23:42
  • $\begingroup$ You only need to read two points to determine the slope of a straight line $\endgroup$
    – edu
    Commented Dec 19, 2018 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.